Submission #1262737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262737		ChuanChen	Traffic (IOI10_traffic)	C++20	100 / 100	537 ms	164772 KiB

traffic

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

typedef long long ll;
const int MAXN = 1e6;
const ll inf = 2e18;

int n, p[MAXN];
vector<int> adj[MAXN];
ll TOT;
ll stag[MAXN]; //#ppl that passes through the edge to my ancestor
ll max_st[MAXN]; //max(stag[i]), give i is my child

pair<int, int> ans = {inf, inf}; //{max #ppl in a road, the seed};

void dfs(int no, int anc){
   for(int v : adj[no]) if(v != anc){
      dfs(v, no);
      stag[no] += stag[v];
      max_st[no] = max(max_st[no], stag[v]);
   }
   stag[no] += p[no];
   pair<int, int> ans_no = make_pair( max(TOT-stag[no], max_st[no]), no );
   ans = min( ans, ans_no );
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   n = N;
   for(int i = 0; i < N; i++) TOT += p[i]=pp[i];
   for(int i = 0; i < N-1; i++){
      adj[S[i]].push_back(D[i]);
      adj[D[i]].push_back(S[i]);
   }
   dfs(0, 0);

   return ans.second;
}

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