Submission #34120

#	Time	Username	Problem	Language	Result	Execution time	Memory
34120		natsukagami	스파이 (JOI13_spy)	C++14	100 / 100	203 ms	18140 KiB

spy

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2005;

int N, M;
vector<int> A[maxn], B[maxn];
int sa[maxn], ta[maxn], sb[maxn], tb[maxn];

int dfs(int v, vector<int> G[], int s[], int t[], int Time = 0) {
	s[v] = Time++;
	for (auto u: G[v])
		Time = dfs(u, G, s, t, Time);
	return t[v] = Time;
}

int sum[maxn][maxn];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		int x; 
		cin >> x; A[x].push_back(i);
		cin >> x; B[x].push_back(i);
	}
	dfs(0, A, sa, ta);
	dfs(0, B, sb, tb);
	for (int i = 1; i <= M; ++i) {
		int u, v; cin >> u >> v;
		++sum[sa[u]][sb[v]];
		--sum[ta[u]][sb[v]];
		--sum[sa[u]][tb[v]];
		++sum[ta[u]][tb[v]];
	}
	// for (int i = 1; i <= N; ++i) cout << sa[i] << ' ' << ta[i] << endl;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j)
		sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
	for (int i = 1; i <= N; ++i) {
		printf("%d\n", sum[sa[i]][sb[i]]);
	}
}

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