oj.uz

Submission #142790

# Submission time Handle Problem Language Result Execution time Memory
142790 2019-08-11T04:01:58 Z gs18103 스파이 (JOI13_spy) C++14
100 / 100
 373 ms 40436 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define fastio ios::sync_with_stdio(false); cin.tie(NULL)
#define INF 2000000000;
#define LINF 1000000000000000000LL
#define mod 1000000007

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

int dp[2020][2020], cnt[2020][2020], pj[2020], pi[2020];
bool chk[2020][2020];

int f(int i, int j) {
	if(i == 0 || j == 0) return 0;
	if(chk[i][j]) return dp[i][j];
	chk[i][j] = true;
	int temp = pj[j];
	dp[i][j] += f(pi[i], j);
	dp[i][j] += f(i, pj[j]);
	dp[i][j] -= f(pi[i], pj[j]);
	dp[i][j] += cnt[i][j];
	return dp[i][j];
}

int main() {
	fastio;
	int n, m;
	cin >> n >> m;
	for(int i = 1, u, v; i <= n; i++) {
		cin >> u >> v;
		pj[i] = u;
		pi[i] = v;
	}
	for(int i = 1; i <= m; i++) {
		int r, s;
		cin >> r >> s;
		cnt[s][r]++;
	}
	for(int i = 1; i <= n; i++) {
		cout << f(i, i) << '\n';
	}
}

Compilation message

spy.cpp: In function 'int f(int, int)':
spy.cpp:23:6: warning: unused variable 'temp' [-Wunused-variable]
  int temp = pj[j];
      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2168 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 4 ms 2040 KB Output is correct
4 Correct 4 ms 1784 KB Output is correct
5 Correct 4 ms 2168 KB Output is correct
6 Correct 4 ms 1784 KB Output is correct
7 Correct 4 ms 2168 KB Output is correct
8 Correct 4 ms 2168 KB Output is correct
9 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 26588 KB Output is correct
2 Correct 137 ms 20344 KB Output is correct
3 Correct 22 ms 19832 KB Output is correct
4 Correct 22 ms 18812 KB Output is correct
5 Correct 34 ms 25976 KB Output is correct
6 Correct 31 ms 20344 KB Output is correct
7 Correct 139 ms 26360 KB Output is correct
8 Correct 43 ms 26488 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 40436 KB Output is correct
2 Correct 230 ms 24964 KB Output is correct
3 Correct 130 ms 32572 KB Output is correct
4 Correct 138 ms 36932 KB Output is correct
5 Correct 163 ms 40316 KB Output is correct
6 Correct 119 ms 25012 KB Output is correct
7 Correct 373 ms 40312 KB Output is correct
8 Correct 240 ms 40404 KB Output is correct