Submission #321111

#	Time	Username	Problem	Language	Result	Execution time	Memory
321111		daringtrifles	Traffic (IOI10_traffic)	C++17	50 / 100	572 ms	206436 KiB

traffic

//control+option+n to run!
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define FOR(i, a, b) for (signed long long i = (signed long long)(a); i < (signed long long)(b); i++)
#define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--)
#define vll vector<long long>
#define sll set<long long>
#define ld long double
#define inf 1000000000000000000
#define mll multiset<long long>
#define vpll vector<pll>
#define nn << "\n"
#define ss << " "
#define F(i, b) for (ll i = 0; i < b; i++)
//10^8 operations per second
//greatest int is 2,147,483,647
//greates long long is 9.22337204e18

//ALL FUNCTIONS SHOULD BE LL!!!!

vll v[3000000];
int x[3000000];
vector <bool> visited(3000000);
vll sz(3000000);
void dfs(int node){
    
    visited[node]=1;
    ll co=0;
    for(auto i:v[node]){
        
        if (!visited[i]){
                       co++;
            dfs(i);
            sz[node]+=sz[i];
            sz[node]+=x[i];
        }
    }
    

}

int LocateCentre(int n, int p[], int s[], int d[])
{
    
    FOR(i,0,n-1){
        v[s[i]].pb(d[i]);
        v[d[i]].pb(s[i]);
    }
    FOR(i,0,n){
       x[i]+=p[i];
    }
    dfs(0);
    ll ans=inf;
    ll sum=0;
    
    FOR(i,0,n){
       sum+=p[i];            
    }
    ll accans=inf;
    FOR(i,0,n){
        if (ans>max(sz[i],sum-sz[i]-p[i])) {
                       accans=i;
                       ans=max(sz[i],sum-sz[i]-p[i]);
                       
                       
        }
       // cout<<sz[i] nn;
        //cout<<max(sz[i],sum-sz[i]-p[i]) nn;
        
    }
    return accans;
}

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