제출 #573378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573378		Trisanu_Das	Traffic (IOI10_traffic)	C++17	100 / 100	966 ms	158912 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
 
int peeps = 0;
vector<int> adj[(int)1e6], city((int)1e6), peepsInPath((int)1e6), numOfChild((int)1e6);
 
void dfs(int u, int parent){
    for (auto v: adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
		numOfChild[u] += numOfChild[v]; peepsInPath[u] = max(peepsInPath[u], numOfChild[v]);
	}
	peepsInPath[u] = max(peepsInPath[u], peeps - numOfChild[u] - city[u]); numOfChild[u] += city[u];
}
 
int LocateCentre(int n, int p[], int s[], int d[]){
  for(int i = 0; i < n; i++){
    peeps += p[i]; city[i] = p[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, -1);
  int ans = -1, cong = INT_MAX;
  for(int i = 0; i < n; i++){
    if(peepsInPath[i] < cong){
      ans = i; cong = peepsInPath[i];
    }
  }
  return ans;
}

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