Submission #1198501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198501		AMel0n	Traffic (IOI10_traffic)	C++20	0 / 100	0 ms	320 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 subsum = 0;
    for(auto c: adj[n]) {
        if (c != p) {
            int s = dfs(c, n);
            if (mn > s) {
                mn = s;
                res = n;
            }
            subsum += s;
        }
    }
    if (mn > tot - subsum - P[n]) {
        mn = tot - subsum - P[n];
        res = n;
    }
    return subsum + 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);
    
// }

// 5th try :(

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