Submission #886005

#	Time	Username	Problem	Language	Result	Execution time	Memory
886005		JakobZorz	Traffic (IOI10_traffic)	C++17	100 / 100	907 ms	245052 KiB

traffic

#include"traffic.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

int n;
vector<int>nodes[1000000];
int people[1000000];
vector<int>ch[1000000];
ll pps[1000000];

void dfs(int node,int par){
    pps[node]=people[node];
    for(int ne:nodes[node]){
        if(ne==par)
            continue;
        dfs(ne,node);
        ch[node].push_back(ne);
        pps[node]+=pps[ne];
    }
}

int LocateCentre(int N,int pp[],int S[],int D[]){
    n=N;
    for(int i=0;i<n;i++)
        people[i]=pp[i];
    for(int i=0;i<n-1;i++){
        nodes[S[i]].push_back(D[i]);
        nodes[D[i]].push_back(S[i]);
    }
    dfs(0,0);
    ll res=pps[0];
    int resn=0;
    
    int node=0;
    while(true){
        ll cres=pps[0]-pps[node];
        int next=0;
        for(int c:ch[node]){
            if(pps[c]>cres){
                cres=pps[c];
                next=c;
            }
        }
        //cout<<cres<<" "<<res<<"\n";
        if(cres<res){
            res=cres;
            resn=node;
        }else
            break;
        node=next;
    }
    
    return resn;
}

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