oj.uz

Submission #34000

# Submission time Handle Problem Language Result Execution time Memory
34000 2017-11-06T02:05:29 Z minkank 스파이 (JOI13_spy) C++14
10 / 100
 146 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) 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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18004 KB Output is correct
2 Correct 13 ms 18004 KB Output is correct
3 Correct 13 ms 18004 KB Output is correct
4 Correct 19 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 16 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18168 KB Output is correct
2 Runtime error 19 ms 18168 KB Execution killed because of forbidden syscall writev (20)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 18164 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -