제출 #495546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495546		PiejanVDC	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	332 KiB

traffic

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

vector<vector<int>>adj;
int n;
vector<int>v;

vector<int>mx,total;

int root_dfs(int u, int e = -1) {
    int w = v[u];
    for(auto z : adj[u]) {
        if(z == e) continue;
        int curr = root_dfs(z,u);
        w+=curr;
        mx[u] = max(mx[u],curr);
    }
    return total[u] = w;
}

int best, mn = INT_MAX;

void dfs(int u, int sum, int e = -1) {
    if(max(mx[u],sum) < mn) {
        mn = max(mx[u],sum);
        best = u+1;
    }
    for(auto z : adj[u]) {
        if(z == e) continue;
        int nw = total[u] - total[z] + sum;
        dfs(z,nw,u);
    }
}

int LocateCentre(int nn, int p[], int s[], int d[]) {
    n=nn;
    adj.resize(n);
    v.resize(n);
    for(int i = 0 ; i < n ; i++) v[i] = p[i];
    mx.resize(n,0);
    total.resize(n,0);
    for(int i = 0 ; i < n-1 ; i++) {
        adj[s[i]-1].push_back(d[i]-1);
        adj[d[i]-1].push_back(s[i]-1);
    }
    root_dfs(0);
    dfs(0,0);
    return best;
}

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