제출 #730771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730771		Jarif_Rahman	Traffic (IOI10_traffic)	C++17	100 / 100	891 ms	170740 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, sum = 0;
vector<vector<int>> tree;
vector<int> P, PP;
int mn = 2e9+1, ans = -1;

void dfs(int nd, int ss){
    int mx = 0, up = sum-P[nd];
    for(int x: tree[nd]) if(x != ss) dfs(x, nd), PP[nd]+=PP[x], mx = max(mx, PP[x]), up-=PP[x];
    mx = max(mx, up);
    if(mx < mn) mn = mx, ans = nd;
}

int LocateCentre(int _n, int _P[], int U[], int V[]){
    swap(n, _n);
    tree.resize(n);
    P.resize(n);
    for(int i = 0; i < n; i++) P[i] = _P[i];
    PP = P;
    for(int i = 0; i < n-1; i++){
        tree[U[i]].pb(V[i]);
        tree[V[i]].pb(U[i]);
    }
    for(int x: P) sum+=x;
    dfs(0, -1);
    return ans;
}

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