Submission #315922

#	Time	Username	Problem	Language	Result	Execution time	Memory
315922		aris12345678	Traffic (IOI10_traffic)	C++17	100 / 100	1320 ms	156776 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxN = 1e6+5;
const int mod = 1e9+7;
const int inf = 1e9;

vector<int> adj[mxN];
int res = 0, ans = 0, num = 2e9+5, f[mxN], traf[mxN], pos[mxN];

void dfs(int u, int e) {
    for(int v : adj[u]) {
        if(v == e) continue;
        dfs(v, u);
        traf[u] += traf[v];
        pos[u] = max(pos[u], traf[v]);
    }
    pos[u] = max(pos[u], res-traf[u]-f[u]);
    traf[u] += f[u];
}

int LocateCentre(int n, int p[], int s[], int d[]) {
    for(int i = 0; i < n-1; i++) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
        f[i] = p[i];
        res += p[i];
    }
    f[n-1] = p[n-1];
    res += p[n-1];
    dfs(0, -1);
    for(int i = 0; i < n; i++) {
        if(num > pos[i]) { num = pos[i]; ans = i; }
    }
    return ans;
}

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