Submission #427432

#	Time	Username	Problem	Language	Result	Execution time	Memory
427432		cpp219	Traffic (IOI10_traffic)	C++14	100 / 100	1666 ms	168316 KiB

traffic

#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],sum;
void DFS(ll u,ll p){
    child[u] = a[u];
    ll res = -inf;
    for (auto i : g[u]){
        if (i == p) continue;
        DFS(i,u); child[u] += child[i];
        res = max(res,child[i]);
    }
    res = max(res,sum - child[u]);
    mn = min(mn,res);
    //cout<<u<<" "<<mn<<" "<<res<<"\n";
    if (res == mn) chosen = u;
}

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]);
    }
    DFS(0,-1);
    //for (ll i = 0;i < n;i++) cout<<child[i]<<" ";
    //exit(0);
    return chosen;
}

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"
      |

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25