제출 #1113524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113524		Zflop	Traffic (IOI10_traffic)	C++14	100 / 100	820 ms	155112 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int NMAX = (int)1e6 + 1;
vector<int>ad[NMAX];
int sum[NMAX],A[NMAX],ans = (int)1e9,id = 0;
void dfs(int node,int parent) {
	for (auto& x : ad[node])
		if (x != parent) {
			dfs(x,node); 
			sum[node] += sum[x];
			}
	}

void dfs1(int node,int parent,int sus) {
	int cost = sus;
	int cr = cost;
	for (auto& x : ad[node])
		if (x != parent) {
			cost += sum[x]; 
			cr = max(cr,sum[x]);
			}
	if (ans > cr) {
		ans = cr;
		id = node;
		}
	//cout << node << ' ' << parent << ' ' << sus << ' ' << cost << '\n';
	for (auto& x : ad[node])
		if (x != parent)
			dfs1(x,node,cost - sum[x] + A[node]);
	}

int LocateCentre(int N,int P[],int S[],int D[]) {
	for (int i = 0; i < N;++i) 
		sum[i] = A[i] = P[i];
	for (int i = 0; i < N - 1;++i) {
		ad[S[i]].push_back(D[i]);
		ad[D[i]].push_back(S[i]);
		}
	dfs(0,0);
	dfs1(0,0,0);
	return id;
	}

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