Submission #1198494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198494		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;
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);
    }
    mn = min(mn, ss + (tot - ss - P[n]));
    return ss + P[n];
}

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


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

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