Submission #427331

#	Time	Username	Problem	Language	Result	Execution time	Memory
427331		cpp219	Traffic (IOI10_traffic)	C++14	Compilation error	0 ms	0 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 = 1e12 + 9;
const ll inf = 1e9 + 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;
}

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"
      | 
traffic.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.000000000009e+12' to '2147483647' [-Woverflow]
   11 | const ll N = 1e12 + 9;
      |              ~~~~~^~~
traffic.cpp:15:14: error: size of array 'g' exceeds maximum object size '9223372036854775807'
   15 | vector<ll> g[N];
      |              ^
traffic.cpp:16:8: error: size of array 'a' exceeds maximum object size '9223372036854775807'
   16 | ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
      |        ^
traffic.cpp:16:33: error: size of array 'child' exceeds maximum object size '9223372036854775807'
   16 | ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
      |                                 ^
traffic.cpp:16:46: error: size of array 'InitChild' exceeds maximum object size '9223372036854775807'
   16 | ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
      |                                              ^
traffic.cpp:17:11: error: size of array 's' exceeds maximum object size '9223372036854775807'
   17 | set<LL> s[N];
      |           ^