제출 #373311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373311		No_Ice	Traffic (IOI10_traffic)	C++17	50 / 100	5019 ms	29952 KiB

traffic

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

#define ll long long

const int mxN = 1e6;
const ll INF = 1e17;

int N;
vector<int> adj[mxN];
ll a;

ll dfs(int u, int pre, int p[]) {
	ll sum = 0;
	for (int v : adj[u]) {
		if (v != pre) {
			ll temp = sum;
			sum += p[v];
			sum += dfs(v, u, p);
			a = max(a, sum - temp);
		}
	}

	return sum;
}

int LocateCentre(int N, int p[], int s[], int d[]) {
	for (int i=0; i < N-1; i++) {
		adj[s[i]].push_back(d[i]);
		adj[d[i]].push_back(s[i]);
	}

	ll ans = INF;
	int ans1 = 0;
	for (int i=0; i < N; i++) {
		a = 0;
		dfs(i, -1, p);
		if (a < ans) {
			ans = a;
			ans1 = i;
		}
	}

	return ans1;
}

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