Submission #34001

#	Time	Username	Problem	Language	Result	Execution time	Memory
34001		minkank	스파이 (JOI13_spy)	C++14	100 / 100	199 ms	18168 KiB

spy

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70