제출 #448575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448575		Deepesson	Traffic (IOI10_traffic)	C++17	100 / 100	1076 ms	165444 KiB

traffic

#include <bits/stdc++.h>
#define MAX 1210000
typedef std::pair<long long,long long> pii;
std::vector<long long> con[MAX];
long long res = 2e9+10;
long long ind;
int* pop;
long long soma_total = 0;
long long dfs(long long pos,long long prev,long long dist){
    long long max = 0;
    long long soma = pop[pos];
    for(auto&x:con[pos]){
        if(x!=prev){
            long long r = dfs(x,pos,dist+(long long)pop[pos]);
            max=std::max(max,r);
            soma+=r;
        }
    }
    max=std::max(max,soma_total-soma);
    if(max<res){
        res=std::min(res,max);
        ind=pos;
    }
    return soma;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   pop=pp;
   for(auto&x:con)x.clear();
   res=2e9+10;
   for(int i=0;i!=N-1;++i){
        con[S[i]].push_back(D[i]);
        con[D[i]].push_back(S[i]);
   }
   for(int i=0;i!=N;++i)soma_total+=pp[i];
   int start = 0;
   for(int i=0;i!=N;++i)if(con[i].size()==1)start=i;
   dfs(start,-1,0);
   return ind;
}

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