Submission #1869788
Source Code Expand
//while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle const int nax=200*1007; using ll=long long; int n; vector < pair<int,ll> > graf[nax]; ll tab[nax]; ll wyn; int bylcen[nax]; vector <int> spo; int roz[nax]; int maxroz[nax]; vector < pair <int,ll> > ter; vector < pair <ll , pair <int,int> > > kra; int oj[nax]; int fin(int v) { if (v!=oj[v]) oj[v]=fin(oj[v]); return oj[v]; } bool mniej(pair <int,ll> a, pair <int,ll> b) { return a.second<b.second; } void dfs1(int v, int oj) { roz[v]=1; maxroz[v]=0; spo.push_back(v); for (auto i : graf[v]) { if(i.first==oj || bylcen[i.first]) continue; dfs1(i.first, v); roz[v]+=roz[i.first]; maxroz[v]=max(maxroz[v], roz[i.first]); } } void dfs2(int v, int oj, ll odl) { ter.push_back({v, odl+tab[v]}); for (auto i : graf[v]) { if(i.first==oj || bylcen[i.first]) continue; dfs2(i.first, v, odl+i.second); } } void szuk(int v) { if (bylcen[v]) return; spo.clear(); dfs1(v, 0); int c=-1; int ss=spo.size(); for (int i : spo) if (2*maxroz[i]<=ss && 2*(ss-roz[i])<=ss) c=i; bylcen[c]=1; ter.clear(); dfs2(c, 0, 0LL); sort(ter.begin(), ter.end(), mniej); for (auto i : ter) kra.push_back({i.second+ter[0].second, {i.first, ter[0].first}}); for (auto i : graf[c]) szuk(i.first); } int main() { scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%lld", &tab[i]); for (int i=1; i<n; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); //a=i; //b=i+1; //c=1; graf[a].push_back({b, c}); graf[b].push_back({a, c}); } szuk(1); for (int i=1; i<=n; i++) oj[i]=i; sort(kra.begin(), kra.end()); for (auto i : kra) { int x=fin(i.second.first); int y=fin(i.second.second); if (x!=y) { oj[x]=y; wyn+=i.first; } } printf("%lld\n", wyn); return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - Tree MST |
User | Stonefeang |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 3090 Byte |
Status | AC |
Exec Time | 901 ms |
Memory | 104160 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:134:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:136:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &tab[i]); ^ ./Main.cpp:140:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &a, &b, &c); ^
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1900 / 1900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
All | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt, 01-58.txt, 01-59.txt, 01-60.txt, 01-61.txt, 01-62.txt, 01-63.txt, 01-64.txt, 01-65.txt, 01-66.txt, 01-67.txt, 01-68.txt, 01-69.txt, 01-70.txt, 01-71.txt, 01-72.txt, 01-73.txt, 01-74.txt, 01-75.txt, 01-76.txt, 01-77.txt, 01-78.txt, 01-79.txt, 01-80.txt, 01-81.txt, 01-82.txt, 01-83.txt, 01-84.txt, 01-85.txt, 01-86.txt, 01-87.txt, 01-88.txt, 01-89.txt, 01-90.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 3 ms | 7680 KB |
01-02.txt | AC | 3 ms | 7680 KB |
01-03.txt | AC | 3 ms | 7680 KB |
01-04.txt | AC | 26 ms | 10676 KB |
01-05.txt | AC | 750 ms | 90464 KB |
01-06.txt | AC | 750 ms | 89056 KB |
01-07.txt | AC | 741 ms | 89440 KB |
01-08.txt | AC | 753 ms | 89440 KB |
01-09.txt | AC | 699 ms | 90976 KB |
01-10.txt | AC | 732 ms | 91232 KB |
01-11.txt | AC | 737 ms | 91360 KB |
01-12.txt | AC | 732 ms | 91232 KB |
01-13.txt | AC | 736 ms | 89056 KB |
01-14.txt | AC | 749 ms | 89952 KB |
01-15.txt | AC | 749 ms | 89440 KB |
01-16.txt | AC | 743 ms | 89056 KB |
01-17.txt | AC | 737 ms | 91616 KB |
01-18.txt | AC | 714 ms | 89696 KB |
01-19.txt | AC | 712 ms | 89696 KB |
01-20.txt | AC | 781 ms | 90464 KB |
01-21.txt | AC | 773 ms | 91488 KB |
01-22.txt | AC | 777 ms | 90592 KB |
01-23.txt | AC | 783 ms | 92640 KB |
01-24.txt | AC | 772 ms | 92512 KB |
01-25.txt | AC | 792 ms | 92000 KB |
01-26.txt | AC | 780 ms | 92256 KB |
01-27.txt | AC | 784 ms | 91488 KB |
01-28.txt | AC | 789 ms | 90968 KB |
01-29.txt | AC | 790 ms | 90708 KB |
01-30.txt | AC | 268 ms | 41576 KB |
01-31.txt | AC | 278 ms | 40940 KB |
01-32.txt | AC | 269 ms | 41324 KB |
01-33.txt | AC | 281 ms | 40808 KB |
01-34.txt | AC | 280 ms | 42728 KB |
01-35.txt | AC | 900 ms | 102872 KB |
01-36.txt | AC | 901 ms | 102624 KB |
01-37.txt | AC | 886 ms | 101600 KB |
01-38.txt | AC | 883 ms | 104040 KB |
01-39.txt | AC | 866 ms | 101728 KB |
01-40.txt | AC | 866 ms | 103392 KB |
01-41.txt | AC | 183 ms | 35948 KB |
01-42.txt | AC | 192 ms | 36844 KB |
01-43.txt | AC | 187 ms | 34796 KB |
01-44.txt | AC | 183 ms | 38124 KB |
01-45.txt | AC | 779 ms | 92128 KB |
01-46.txt | AC | 807 ms | 90976 KB |
01-47.txt | AC | 837 ms | 92000 KB |
01-48.txt | AC | 889 ms | 101576 KB |
01-49.txt | AC | 867 ms | 101592 KB |
01-50.txt | AC | 872 ms | 102496 KB |
01-51.txt | AC | 876 ms | 101472 KB |
01-52.txt | AC | 859 ms | 102888 KB |
01-53.txt | AC | 865 ms | 104160 KB |
01-54.txt | AC | 861 ms | 102240 KB |
01-55.txt | AC | 660 ms | 89188 KB |
01-56.txt | AC | 653 ms | 89444 KB |
01-57.txt | AC | 614 ms | 89312 KB |
01-58.txt | AC | 719 ms | 90852 KB |
01-59.txt | AC | 703 ms | 90720 KB |
01-60.txt | AC | 684 ms | 89312 KB |
01-61.txt | AC | 627 ms | 90084 KB |
01-62.txt | AC | 639 ms | 90848 KB |
01-63.txt | AC | 637 ms | 90084 KB |
01-64.txt | AC | 709 ms | 90596 KB |
01-65.txt | AC | 716 ms | 92512 KB |
01-66.txt | AC | 732 ms | 91232 KB |
01-67.txt | AC | 612 ms | 90212 KB |
01-68.txt | AC | 636 ms | 90336 KB |
01-69.txt | AC | 652 ms | 88676 KB |
01-70.txt | AC | 691 ms | 91236 KB |
01-71.txt | AC | 695 ms | 91492 KB |
01-72.txt | AC | 697 ms | 92000 KB |
01-73.txt | AC | 563 ms | 88544 KB |
01-74.txt | AC | 549 ms | 88544 KB |
01-75.txt | AC | 538 ms | 90596 KB |
01-76.txt | AC | 605 ms | 89188 KB |
01-77.txt | AC | 638 ms | 88672 KB |
01-78.txt | AC | 616 ms | 89316 KB |
01-79.txt | AC | 551 ms | 90592 KB |
01-80.txt | AC | 578 ms | 91740 KB |
01-81.txt | AC | 586 ms | 88928 KB |
01-82.txt | AC | 632 ms | 90980 KB |
01-83.txt | AC | 653 ms | 90720 KB |
01-84.txt | AC | 622 ms | 90468 KB |
01-85.txt | AC | 562 ms | 89188 KB |
01-86.txt | AC | 568 ms | 89184 KB |
01-87.txt | AC | 566 ms | 89828 KB |
01-88.txt | AC | 655 ms | 94176 KB |
01-89.txt | AC | 630 ms | 90932 KB |
01-90.txt | AC | 648 ms | 91108 KB |
sample-01.txt | AC | 3 ms | 7680 KB |
sample-02.txt | AC | 3 ms | 7680 KB |
sample-03.txt | AC | 3 ms | 7680 KB |