제출 #373310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373310		No_Ice	Traffic (IOI10_traffic)	C++17	25 / 100	5046 ms	30700 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 dfs(int u, int pre, int p[]) {
	ll sum = 0;
	for (int v : adj[u]) {
		if (v != pre) {
			ll c_sum = 0;
			c_sum += (ll)p[v];
			c_sum += dfs(v, u, p);
			sum = max(sum, c_sum);
		}
	}

	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++) {
		ll temp = dfs(i, -1, p);
		if (temp < ans) {
			ans = temp;
			ans1 = i;
		}
	}

	return ans1;
}

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