oj.uz

답안 #33999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
33999 2017-11-06T02:03:19 Z minkank 스파이 (JOI13_spy) C++14
10 / 100
 266 ms 65280 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;

int n, m, st[2][N], en[2][N], a[2 * N][2 * 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 <= 4000; ++i) for(int j = 1; j <= 4000; ++j)
		a[i][j] += a[i - 1][j];
	for(int i = 1; i <= 4000; ++i) for(int j = 1; j <= 4000; ++j)
		a[i][j] += a[i][j - 1];
	for(int i = 1; i <= n; ++i) cout << a[st[0][i]][st[1][i]] << '\n';
}

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 66 ms 65112 KB Output is correct
2 Correct 59 ms 65112 KB Output is correct
3 Correct 73 ms 65112 KB Output is correct
4 Correct 53 ms 65112 KB Output is correct
5 Correct 69 ms 65112 KB Output is correct
6 Correct 63 ms 65112 KB Output is correct
7 Correct 53 ms 65112 KB Output is correct
8 Correct 56 ms 65112 KB Output is correct
9 Correct 66 ms 65112 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 65276 KB Output is correct
2 Runtime error 56 ms 65276 KB Execution killed because of forbidden syscall writev (20)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 266 ms 65280 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -