oj.uz

답안 #147137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147137 2019-08-28T01:08:59 Z gs18103 스파이 (JOI13_spy) C++14
100 / 100
 198 ms 36844 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

int pj[2020], pi[2020];
int dp[2020][2020], cnt[2020][2020];
bool chk[2020][2020];
vector <int> ci[2020], cj[2020], ordj, ordi;

void dfsi(int x) {
	if(x)ordi.emplace_back(x);
	for(auto i : ci[x]) {
		dfsi(i);
	}
	return;
}
void dfsj(int x) {
	if(x)ordj.emplace_back(x);
	for(auto i : cj[x]) {
		dfsj(i);
	}
	return;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1, u, v; i <= n; i++) {
		cin >> u >> v;
		pj[i] = u;
		pi[i] = v;
		cj[u].emplace_back(i);
		ci[v].emplace_back(i);
	}
	for(int i = 1; i <= m; i++) {
		int r, s;
		cin >> r >> s;
		cnt[s][r]++;
	}
	dfsi(0);
	dfsj(0);

	for(int i : ordi) {
		for(int j : ordj) {
			dp[i][j] = dp[pi[i]][j] + dp[i][pj[j]] - dp[pi[i]][pj[j]] + cnt[i][j];
		}
	}

	for(int i = 1; i <= n; i++) {
		cout << dp[i][i] << '\n';
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 4 ms 1784 KB Output is correct
4 Correct 4 ms 1656 KB Output is correct
5 Correct 4 ms 1912 KB Output is correct
6 Correct 4 ms 1528 KB Output is correct
7 Correct 4 ms 1912 KB Output is correct
8 Correct 4 ms 1912 KB Output is correct
9 Correct 2 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 22840 KB Output is correct
2 Correct 38 ms 16784 KB Output is correct
3 Correct 35 ms 19704 KB Output is correct
4 Correct 36 ms 18800 KB Output is correct
5 Correct 40 ms 22264 KB Output is correct
6 Correct 37 ms 16636 KB Output is correct
7 Correct 42 ms 22776 KB Output is correct
8 Correct 41 ms 22648 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 36788 KB Output is correct
2 Correct 133 ms 20948 KB Output is correct
3 Correct 140 ms 32632 KB Output is correct
4 Correct 146 ms 36844 KB Output is correct
5 Correct 168 ms 36600 KB Output is correct
6 Correct 123 ms 21288 KB Output is correct
7 Correct 198 ms 36728 KB Output is correct
8 Correct 193 ms 36600 KB Output is correct