Submission #427370

#TimeUsernameProblemLanguageResultExecution timeMemory
427370cpp219Traffic (IOI10_traffic)C++14
50 / 100
668 ms262148 KiB
#pragma GCC optimization "O2" #pragma GCC optimization "unroll-loop" #pragma GCC target ("avx2") #include <bits/stdc++.h> #define ll int #define ld long double #define fs first #define sc second using namespace std; const ll N = 1e6 + 9; const ll inf = 2e9 + 7; const ll Log2 = 20; typedef pair<ll,ll> LL; vector<ll> g[N]; ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum; set<LL> s[N]; void DFSinit(ll u,ll p){ child[u] = a[u]; for (auto i : g[u]){ if (i == p) continue; DFSinit(i,u); child[u] += child[i]; s[u].insert({child[i],i}); } InitChild[u] = child[u]; } void DFS(ll u,ll p){ if (!s[u].empty()){ LL now = *s[u].rbegin(),rm = {sum - child[u],-1}; now = max(now,rm); if (now.fs < mn) mn = now.fs,chosen = u; } for (auto i : g[u]){ if (i == p) continue; s[u].erase({child[i],i}); s[i].insert({sum - child[i],u}); //cout<<child[i]<<" "<<i; exit(0); child[u] = sum - child[i]; child[i] = sum; DFS(i,u); } if (p >= 0){ child[u] = InitChild[u]; s[p].insert({child[u],u}); s[u].erase({child[p],p}); child[p] = InitChild[p]; } } ll LocateCentre(ll sz,ll P[],ll X[],ll Y[]){ n = sz; for (ll i = 0;i < n;i++) a[i] = P[i],sum += a[i]; for (ll i = 0;i < n - 1;i++){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } DFSinit(0,-1); DFS(0,-1); return chosen; } /* ll sz,X[N],Y[N],P[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); #define task "test" if (fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); //freopen(task".out", "w", stdout); } cin>>sz; for (ll i = 0;i < sz;i++) cin>>P[i]; for (ll i = 0;i < sz - 1;i++) cin>>X[i]>>Y[i]; cout<<LocateCentre(sz,P,X,Y); } */

Compilation message (stderr)

traffic.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
traffic.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...