Submission #34120

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34120	2017-11-07T15:30:54 Z	natsukagami	스파이 (JOI13_spy)	C++14	100 / 100	203 ms	18140 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	18004 KB	Output is correct
2	Correct	0 ms	18004 KB	Output is correct
3	Correct	0 ms	18004 KB	Output is correct
4	Correct	0 ms	18004 KB	Output is correct
5	Correct	0 ms	18004 KB	Output is correct
6	Correct	0 ms	18004 KB	Output is correct
7	Correct	0 ms	18004 KB	Output is correct
8	Correct	0 ms	18004 KB	Output is correct
9	Correct	0 ms	18004 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	18136 KB	Output is correct
2	Correct	19 ms	18136 KB	Output is correct
3	Correct	23 ms	18004 KB	Output is correct
4	Correct	16 ms	18004 KB	Output is correct
5	Correct	13 ms	18004 KB	Output is correct
6	Correct	13 ms	18004 KB	Output is correct
7	Correct	9 ms	18136 KB	Output is correct
8	Correct	16 ms	18136 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	18140 KB	Output is correct
2	Correct	99 ms	18136 KB	Output is correct
3	Correct	116 ms	18004 KB	Output is correct
4	Correct	116 ms	18004 KB	Output is correct
5	Correct	136 ms	18004 KB	Output is correct
6	Correct	96 ms	18004 KB	Output is correct
7	Correct	203 ms	18136 KB	Output is correct
8	Correct	193 ms	18136 KB	Output is correct