Submission #339063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339063	2020-12-24T13:57:59 Z	study	Traffic (IOI10_traffic)	C++17	0 / 100	10 ms	16256 KB

traffic

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

const int NB = 1e6+1;

vector<long long> subtree(NB);
vector<bool> vu(NB);
vector<long long> ans(NB);

void dfs1(int node, vector<vector<int>>& adj, int pp[]){
	int sum = 0;
	for (int i:adj[node]){
		if (!vu[i]){
			vu[i] = true;
			dfs1(i,adj,pp);
			sum += subtree[i]+pp[i];
		}
	}
	subtree[node] = sum;
}

void dfs2(int node, vector<vector<int>>& adj, int pp[]){
	for (int i:adj[node]) ans[node] = max(ans[node],subtree[i]+pp[i]);
	for (int i:adj[node]){
		if (!vu[i]){
			vu[i] = true;
			int a = subtree[node], b = subtree[i];
			subtree[node] -= subtree[i];
			subtree[node] -= pp[i];
			subtree[i] += subtree[node]+pp[node];
			dfs2(i,adj,pp);
			subtree[node] = a;
			subtree[i] = b;
		}
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	vector<vector<int>> adj(N);
	for (int i=0; i<N; ++i){
		adj[S[i]].emplace_back(D[i]);
		adj[D[i]].emplace_back(S[i]);
	}
	vu[0] = true;
	dfs1(0,adj,pp);
   vu = vector<bool>(NB);
	vu[0] = true;
   dfs2(0,adj,pp);
	long long mini = LLONG_MAX,idx=0;
	for (int i=0; i<N; ++i){
		if (mini > ans[i]){
			mini = ans[i];
			idx = i;
		}
	}
	return idx;
}

Subtask #1

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16236 KB	Output is correct
2	Correct	10 ms	16236 KB	Output is correct
3	Correct	9 ms	16236 KB	Output is correct
4	Correct	9 ms	16236 KB	Output is correct
5	Correct	9 ms	16236 KB	Output is correct
6	Correct	9 ms	16236 KB	Output is correct
7	Correct	9 ms	16256 KB	Output is correct
8	Correct	10 ms	16236 KB	Output is correct
9	Correct	9 ms	16236 KB	Output is correct
10	Correct	9 ms	16236 KB	Output is correct
11	Correct	10 ms	16236 KB	Output is correct
12	Correct	9 ms	16236 KB	Output is correct
13	Correct	9 ms	16236 KB	Output is correct
14	Correct	9 ms	16236 KB	Output is correct
15	Correct	9 ms	16236 KB	Output is correct
16	Correct	9 ms	16236 KB	Output is correct
17	Correct	9 ms	16236 KB	Output is correct
18	Correct	9 ms	16236 KB	Output is correct
19	Correct	9 ms	16236 KB	Output is correct
20	Correct	9 ms	16236 KB	Output is correct
21	Correct	10 ms	16236 KB	Output is correct
22	Correct	9 ms	16236 KB	Output is correct
23	Incorrect	9 ms	16236 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16236 KB	Output is correct
2	Correct	10 ms	16236 KB	Output is correct
3	Correct	9 ms	16236 KB	Output is correct
4	Correct	9 ms	16236 KB	Output is correct
5	Correct	9 ms	16236 KB	Output is correct
6	Correct	9 ms	16236 KB	Output is correct
7	Correct	9 ms	16256 KB	Output is correct
8	Correct	10 ms	16236 KB	Output is correct
9	Correct	9 ms	16236 KB	Output is correct
10	Correct	9 ms	16236 KB	Output is correct
11	Correct	10 ms	16236 KB	Output is correct
12	Correct	9 ms	16236 KB	Output is correct
13	Correct	9 ms	16236 KB	Output is correct
14	Correct	9 ms	16236 KB	Output is correct
15	Correct	9 ms	16236 KB	Output is correct
16	Correct	9 ms	16236 KB	Output is correct
17	Correct	9 ms	16236 KB	Output is correct
18	Correct	9 ms	16236 KB	Output is correct
19	Correct	9 ms	16236 KB	Output is correct
20	Correct	9 ms	16236 KB	Output is correct
21	Correct	10 ms	16236 KB	Output is correct
22	Correct	9 ms	16236 KB	Output is correct
23	Incorrect	9 ms	16236 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16236 KB	Output is correct
2	Correct	10 ms	16236 KB	Output is correct
3	Correct	9 ms	16236 KB	Output is correct
4	Correct	9 ms	16236 KB	Output is correct
5	Correct	9 ms	16236 KB	Output is correct
6	Correct	9 ms	16236 KB	Output is correct
7	Correct	9 ms	16256 KB	Output is correct
8	Correct	10 ms	16236 KB	Output is correct
9	Correct	9 ms	16236 KB	Output is correct
10	Correct	9 ms	16236 KB	Output is correct
11	Correct	10 ms	16236 KB	Output is correct
12	Correct	9 ms	16236 KB	Output is correct
13	Correct	9 ms	16236 KB	Output is correct
14	Correct	9 ms	16236 KB	Output is correct
15	Correct	9 ms	16236 KB	Output is correct
16	Correct	9 ms	16236 KB	Output is correct
17	Correct	9 ms	16236 KB	Output is correct
18	Correct	9 ms	16236 KB	Output is correct
19	Correct	9 ms	16236 KB	Output is correct
20	Correct	9 ms	16236 KB	Output is correct
21	Correct	10 ms	16236 KB	Output is correct
22	Correct	9 ms	16236 KB	Output is correct
23	Incorrect	9 ms	16236 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16236 KB	Output is correct
2	Correct	10 ms	16236 KB	Output is correct
3	Correct	9 ms	16236 KB	Output is correct
4	Correct	9 ms	16236 KB	Output is correct
5	Correct	9 ms	16236 KB	Output is correct
6	Correct	9 ms	16236 KB	Output is correct
7	Correct	9 ms	16256 KB	Output is correct
8	Correct	10 ms	16236 KB	Output is correct
9	Correct	9 ms	16236 KB	Output is correct
10	Correct	9 ms	16236 KB	Output is correct
11	Correct	10 ms	16236 KB	Output is correct
12	Correct	9 ms	16236 KB	Output is correct
13	Correct	9 ms	16236 KB	Output is correct
14	Correct	9 ms	16236 KB	Output is correct
15	Correct	9 ms	16236 KB	Output is correct
16	Correct	9 ms	16236 KB	Output is correct
17	Correct	9 ms	16236 KB	Output is correct
18	Correct	9 ms	16236 KB	Output is correct
19	Correct	9 ms	16236 KB	Output is correct
20	Correct	9 ms	16236 KB	Output is correct
21	Correct	10 ms	16236 KB	Output is correct
22	Correct	9 ms	16236 KB	Output is correct
23	Incorrect	9 ms	16236 KB	Output isn't correct
24	Halted	0 ms	0 KB	-