제출 #1198499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198499		AMel0n	Traffic (IOI10_traffic)	C++20	50 / 100	267 ms	133320 KiB

traffic

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first 
// #define S second

#include "traffic.h"

int N;
vector<int> P;

int tot, mn = INT_MAX, res = -1;
vector<vector<int>> adj;

int dfs(int n, int p) {
    int ss = 0;
    for(auto c: adj[n]) {
        if (c != p) ss += dfs(c, n);
    }
    if (mn > max(ss, (tot - ss - P[n]))) {
        mn = max(ss, (tot - ss - P[n]));
        res = n;
    }
    return ss + P[n];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    ::N = N;
    adj.resize(N);
    P.resize(N);
    FOR(i, N) P[i] = pp[i];
    tot = accumulate(all(P), 0);
    FOR(i, N-1) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    dfs(0,0);
    return res;
}


// signed main() {
//     cin.tie(0); ios::sync_with_stdio(false);
    
// }

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