Submission #463502

#	Time	Username	Problem	Language	Result	Execution time	Memory
463502		fuad27	Traffic (IOI10_traffic)	C++14	0 / 100	34 ms	63180 KiB

traffic

#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define vii vector<pair<int, int>>
#define vi vector<int>
#define vl vector<long long>
#define vll vector<pair<long long, long long>>
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i = a;i<b;i++)
#define f first
#define s second
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);
#define start int tt;cin>>tt;rep(testcase, 1, tt)
#define print(k) cout<<"Case #"<<testcase<<": "<<k<<"\n";
#define endl "\n"
#define DEBUG(k) cerr<<k<<"\n";
#define MAX 2000000
vl v[MAX];
int x[MAX];
vector <bool> visited(MAX, false);
vl sz(MAX);
void dfs(int at){
    
    visited[at]=1;
    ll cnt=0;
    for(auto i:v[at]){
        
        if (!visited[i]){
            cnt++;
            dfs(i);
            sz[at]+=sz[i];
            sz[at]+=x[i];
        }
    }
}
 
int LocateCentre(int n, int p[], int s[], int d[])
{
    
    rep(i,0,n-1){
        v[s[i]].pb(d[i]);
        v[d[i]].pb(s[i]);
    }
    rep(i,0,n){
       x[i]+=p[i];
    }
    dfs(0);
    ll ans=MAX;
    ll sum=0;
    
    rep(i,0,n){
       sum+=p[i];            
    }
    ll correct_ans=MAX;
    rep(i,0,n){
        if (ans>max(sz[i],sum-sz[i]-p[i])) {
                       correct_ans=i;
                       ans=max(sz[i],sum-sz[i]-p[i]);
                       
                       
        }
    }
    return correct_ans;
}

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