Submission #722050

#	Time	Username	Problem	Language	Result	Execution time	Memory
722050		TheSahib	Traffic (IOI10_traffic)	C++17	100 / 100	1117 ms	182432 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX = 1e6 + 6;

vector<int> g[MAX];
int arr[MAX];
ll sub[MAX];

void dfs1(int node, int p){
    sub[node] = arr[node];
    for(int to:g[node]){
        if(to == p) continue;
        dfs1(to, node);
        sub[node] += sub[to];
    }
}

ll ans[MAX];

void dfs2(int node, int p){
    ans[node] = max(ans[node], sub[0] - sub[node]);
    for(int to:g[node]){
        if(to == p) continue;
        dfs2(to, node);
        ans[node] = max(ans[node], sub[to]);
    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for (int i = 0; i < N; i++)
    {
        arr[i] = pp[i];
    }
    for (int i = 0; i < N - 1; i++)
    {
        g[S[i]].emplace_back(D[i]);
        g[D[i]].emplace_back(S[i]);
    }
    dfs1(0, 0);
    dfs2(0, 0);
    int a = 0;
    for (int i = 0; i < N; i++)
    {
        if(ans[i] <= ans[a]){
            a = i;
        }
    }
    return a;
}

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