Submission #34001

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34001	2017-11-06T02:06:24 Z	minkank	스파이 (JOI13_spy)	C++14	100 / 100	199 ms	18168 KB

spy

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

const int N = 2e3 + 5;

int n, m, st[2][N], en[2][N], a[N][N], cnt, root[2];
vector<int> edge[2][N];


void dfs(int type, int u, int p) {
	st[type][u] = ++cnt;
	for(int i = 0; i < edge[type][u].size(); ++i) {
		int v = edge[type][u][i];
		if(v == p) continue;
		dfs(type, v, u);
	}
	en[type][u] = cnt;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		int pa, pb;
		cin >> pa >> pb;
		if(pa == 0) root[0] = i;
		else edge[0][pa].push_back(i);
		if(pb== 0) root[1] = i;
		else edge[1][pb].push_back(i);
	}
	for(int i = 0; i <= 1; ++i) cnt = 0, dfs(i, root[i], root[i]);
	for(int i = 1; i <= m; ++i) {
		int x, y; cin >> x >> y;
		a[st[0][x]][st[1][y]]++; a[st[0][x]][en[1][y] + 1]--;
		a[en[0][x] + 1][st[1][y]]--; a[en[0][x] + 1][en[1][y] + 1]++;
	}
	for(int i = 1; i <= 2000; ++i) for(int j = 1; j <= 2000; ++j)
		a[i][j] += a[i - 1][j];
	for(int i = 1; i <= 2000; ++i) for(int j = 1; j <= 2000; ++j)
		a[i][j] += a[i][j - 1];
	for(int i = 1; i <= n; ++i) printf("%d\n", a[st[0][i]][st[1][i]]);
}

Compilation message

spy.cpp: In function 'void dfs(int, int, int)':
spy.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edge[type][u].size(); ++i) {
                   ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	18004 KB	Output is correct
2	Correct	19 ms	18004 KB	Output is correct
3	Correct	16 ms	18004 KB	Output is correct
4	Correct	16 ms	18004 KB	Output is correct
5	Correct	13 ms	18004 KB	Output is correct
6	Correct	23 ms	18004 KB	Output is correct
7	Correct	9 ms	18004 KB	Output is correct
8	Correct	19 ms	18004 KB	Output is correct
9	Correct	16 ms	18004 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	18164 KB	Output is correct
2	Correct	19 ms	18168 KB	Output is correct
3	Correct	13 ms	18004 KB	Output is correct
4	Correct	13 ms	18004 KB	Output is correct
5	Correct	9 ms	18004 KB	Output is correct
6	Correct	13 ms	18004 KB	Output is correct
7	Correct	19 ms	18136 KB	Output is correct
8	Correct	23 ms	18136 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	18168 KB	Output is correct
2	Correct	93 ms	18164 KB	Output is correct
3	Correct	113 ms	18004 KB	Output is correct
4	Correct	123 ms	18004 KB	Output is correct
5	Correct	153 ms	18004 KB	Output is correct
6	Correct	96 ms	18004 KB	Output is correct
7	Correct	189 ms	18136 KB	Output is correct
8	Correct	199 ms	18136 KB	Output is correct