Submission #33994

#	Time	Username	Problem	Language	Result	Execution time	Memory
33994		aome	스파이 (JOI13_spy)	C++14	100 / 100	163 ms	6608 KiB

spy

#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 j = 1; j <= n; ++j) sum[j] += sum[j - 1];
		cal(i);
	}
	for (int i = 1; i <= n; ++i) printf("%d\n", res[i]);
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70