oj.uz

Submission #33992

# Submission time Handle Problem Language Result Execution time Memory
33992 2017-11-06T01:25:27 Z aome 스파이 (JOI13_spy) C++14
10 / 100
 199 ms 5516 KB 
#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 i = 1; i <= n; ++i) sum[i] += sum[i - 1];
		cal(i);
	}
	for (int i = 1; i <= n; ++i) cout << res[i] << '\n';
}

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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2480 KB Output is correct
2 Runtime error 53 ms 2480 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 199 ms 5516 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -