제출 #236364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236364		nicolaalexandra	Traffic (IOI10_traffic)	C++14	100 / 100	1212 ms	156792 KiB

traffic

#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000000000000LL
using namespace std;

vector <int> L[DIM];
long long sum[DIM];
int fth[DIM];

//int p[DIM],s[DIM],d[DIM];
//int n,i;

void dfs (int nod, int tata){

    fth[nod] = tata;
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            sum[nod] += sum[vecin];
        }
}

int LocateCentre (int n, int p[], int s[], int d[]){

    for (int i=0;i<n-1;i++){
        s[i]++, d[i]++;
        L[s[i]].push_back(d[i]);
        L[d[i]].push_back(s[i]);
    }

    long long sum_total = 0;
    for (int i=1;i<=n;i++){
        sum[i] = p[i-1];
        sum_total += sum[i];
    }

    dfs (1,0);

    long long mini = INF;
    int sol = 0;
    for (int i=1;i<=n;i++){

        long long maxi = 0;
        for (auto vecin : L[i]){
            if (vecin == fth[i])
                continue;
            maxi = max (maxi,sum[vecin]);
        }

        maxi = max (maxi,sum_total - sum[i]);

        if (maxi < mini){
            mini = maxi;
            sol = i;
        }
    }

    return sol - 1;

}

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