Submission #33994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
33994	2017-11-06T01:28:34 Z	aome	스파이 (JOI13_spy)	C++14	100 / 100	163 ms	6608 KB

spy

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

const int N = 2005;

int n, m, r[2];
int st[N], ed[N];
int sum[N], res[N];
vector<int> G[2][N];
vector<int> query[N];

int TIME;

void dfs(int u) {
	st[u] = ++TIME; for (auto v : G[1][u]) dfs(v); ed[u] = TIME;
}

void cal(int u) {
	res[u] += sum[st[u]];
	for (auto v : G[0][u]) cal(v);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		if (!x) r[0] = i; else G[0][x].push_back(i);
		if (!y) r[1] = i; else G[1][y].push_back(i);	
	}
	for (int i = 1; i <= m; ++i) {
		int x, y; cin >> x >> y;
		query[x].push_back(y);
	}
	dfs(r[1]);
	for (int i = 1; i <= n; ++i) {
		memset(sum, 0, sizeof sum);
		for (auto j : query[i]) {
			int l = st[j], r = ed[j];
			sum[l]++, sum[r + 1]--;
		}
		for (int j = 1; j <= n; ++j) sum[j] += sum[j - 1];
		cal(i);
	}
	for (int i = 1; i <= n; ++i) printf("%d\n", res[i]);
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2348 KB	Output is correct
2	Correct	0 ms	2348 KB	Output is correct
3	Correct	0 ms	2348 KB	Output is correct
4	Correct	0 ms	2348 KB	Output is correct
5	Correct	0 ms	2348 KB	Output is correct
6	Correct	0 ms	2348 KB	Output is correct
7	Correct	0 ms	2348 KB	Output is correct
8	Correct	0 ms	2348 KB	Output is correct
9	Correct	0 ms	2348 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	2480 KB	Output is correct
2	Correct	59 ms	2480 KB	Output is correct
3	Correct	9 ms	2348 KB	Output is correct
4	Correct	9 ms	2348 KB	Output is correct
5	Correct	13 ms	2480 KB	Output is correct
6	Correct	13 ms	2480 KB	Output is correct
7	Correct	16 ms	2480 KB	Output is correct
8	Correct	13 ms	2480 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	5516 KB	Output is correct
2	Correct	143 ms	6608 KB	Output is correct
3	Correct	116 ms	4980 KB	Output is correct
4	Correct	109 ms	6356 KB	Output is correct
5	Correct	129 ms	5384 KB	Output is correct
6	Correct	96 ms	6568 KB	Output is correct
7	Correct	123 ms	5648 KB	Output is correct
8	Correct	143 ms	5648 KB	Output is correct