Submission #673777

#	Time	Username	Problem	Language	Result	Execution time	Memory
673777		Cookie	Traffic (IOI10_traffic)	C++14	100 / 100	911 ms	178532 KiB

traffic

#include<bits/stdc++.h>
 
using namespace std;
 #include "traffic.h"
 
 
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("ss.inp");
ofstream fout("ss.out");
#define pii pair<int, int>
#define pll pair<ll, ll>
 
const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 1e6, mxq = 1e5, sq = 800, mxm = 1e5;
int n;
vt<int>adj[mxn + 1];
ll sm[mxn + 1], aa[mxn + 1], all = 0, s[mxn + 1], d[mxn + 1];
ll ans = 1e16, id = -1;
void dfs(int s, int pre){
    sm[s] = aa[s];
    ll mx = 0;
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        sm[s] += sm[i]; mx = max(mx, sm[i]);
        }
    }
    mx = max(mx, all - sm[s]);
    
    if(mx < ans){
        ans = mx; id = s;
    }
}
int LocateCentre(int n, int a[], int s[], int d[]) {
   
    for(int i = 0; i < n; i++){
        aa[i] = a[i];
        all += 1LL * a[i]; 
    }
    forr(i, 0, n - 1){
        
        adj[s[i]].pb(d[i]); adj[d[i]].pb(s[i]);
    }
    dfs(0, -1);
    return(id);
}

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