제출 #1275523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275523		kawhiet	Traffic (IOI10_traffic)	C++20	100 / 100	621 ms	164932 KiB

traffic

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

constexpr int N = 1e6 + 1;

vector<int> a;

int64_t sz[N], parent[N];
vector<int> g[N];

void dfs(int u, int p) {
    sz[u] += a[u];
    parent[u] = p;
    for (auto v : g[u]) {
        if (v != p) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int LocateCentre(int n, int A[], int s[], int d[]) {
    a.resize(n);
    for (int i = 0; i < n; i++) {
      a[i] = A[i];
    }
    for (int i = 0; i < n - 1; i++) {
        g[s[i]].push_back(d[i]);
        g[d[i]].push_back(s[i]);
    }
    dfs(0, -1);
    int64_t sum = accumulate(a.begin(), a.end(), 0LL);
    int mn = 2e9, ans = -1;
    for (int u = 0; u < n; u++) {
        int64_t cur = 0;
        for (auto v : g[u]) {
            if (v == parent[u]) {
                cur = max(cur, sum - sz[u]);
            } else {
                cur = max(cur, sz[v]);
            }
        }
        if (cur < mn) {
            mn = cur;
            ans = u;
        }
    }
    return ans;
}

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