제출 #888618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888618		Sir_Ahmed_Imran	Traffic (IOI10_traffic)	C++17	100 / 100	720 ms	164688 KiB

traffic

                              ///~~~LOTA~~~///
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define N 1000001
long long z[N];
long long x[N];
vector<int> a[N];
int dp[N];
void dfs(int v,int u){
    dp[v]=x[v];
    for(auto& i:a[v]){
        if(i==u) continue;
        dfs(i,v);
        dp[v]+=dp[i];
    }
}
int DFS(int v,int u){
    int k=N-1;
    for(auto& i:a[v]){
        if(i==u) continue;
        if(dp[i]>dp[k]) k=i;
        z[v]+=dp[i];
    }
    if(z[v]-dp[k]<dp[k] && k<N-1){
        z[k]=z[v]-dp[k]+x[k];
        return DFS(k,v);
    }
    return v;
}
int LocateCentre(int n,int p[],int s[],int d[]){
    for(int i=0;i<n-1;i++){
        x[i]=p[i];
        a[s[i]].push_back(d[i]);
        a[d[i]].push_back(s[i]);
    }
    x[n-1]=p[n-1];
    dfs(0,-1);
    z[0]=x[0];
    return DFS(0,-1);
}

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