oj.uz

답안 #34120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34120 2017-11-07T15:30:54 Z natsukagami 스파이 (JOI13_spy) C++14
100 / 100
 203 ms 18140 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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