oj.uz

답안 #34001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34001 2017-11-06T02:06:24 Z minkank 스파이 (JOI13_spy) C++14
100 / 100
 199 ms 18168 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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