Submission #797458

#	Time	Username	Problem	Language	Result	Execution time	Memory
797458		Liudas	Traffic (IOI10_traffic)	C++17	100 / 100	749 ms	137168 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector<vector<int>> g;
vector<int> sz, mx;
 
void dfs(int u, int p)
{
    for (int v: g[u])
    {
        if (v==p) continue;
        dfs(v,u);
        sz[u] += sz[v];
        mx[u] = max(mx[u],sz[v]);
    }
}
 
int LocateCentre(int N, int P[], int S[], int D[])
{
    g.resize(N);
    sz.resize(N);
    mx.resize(N);
    for (int i=0;i<N;i++) sz[i] = P[i];
    for (int i=0;i+1<N;i++)
    {
        g[S[i]].push_back(D[i]);
        g[D[i]].push_back(S[i]);
    }
    dfs(0,-1);
    int SS = sz[0];
    int Q = -1, bst = SS+1;
    for (int i=0;i<N;i++)
    {
        if (mx[i]<SS-sz[i]) mx[i] = SS-sz[i];
        if (bst>mx[i]) bst = mx[i], Q = i;
    }
    return Q;
}

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