oj.uz

답안 #26415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26415 2017-06-30T04:42:32 Z zscoder 스파이 (JOI13_spy) C++14
10 / 100
 216 ms 37404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const int N = 2001;
const int M = 500001;

int p[N];
int q[N];
int r[M];
int s[M];
int common[N][N];
int dp[N][N];

int dfs(int u, int v)
{
	if(dp[u][v] >= 0) return dp[u][v];
	dp[u][v] = common[u][v];
	if(p[u] >= 0)
	{
		dp[u][v] += dfs(p[u], v);
	}
	if(q[v] >= 0)
	{
		dp[u][v] += dfs(u, q[v]);
	}
	if(p[u] >= 0 && q[v] >= 0)
	{
		dp[u][v] -= dfs(p[u], q[v]);
	}
	return dp[u][v];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	{
		cin >> p[i] >> q[i];
		p[i]--; q[i]--;
	}
	
	for(int i = 0; i < m; i++)
	{
		cin >> r[i] >> s[i];
		r[i]--; s[i]--;
		common[r[i]][s[i]]++;
	}
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < n; i++)
	{
		cout << dfs(i, i) << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 37384 KB Output is correct
2 Correct 3 ms 37384 KB Output is correct
3 Correct 3 ms 37384 KB Output is correct
4 Correct 3 ms 37384 KB Output is correct
5 Correct 0 ms 37384 KB Output is correct
6 Correct 0 ms 37384 KB Output is correct
7 Correct 6 ms 37384 KB Output is correct
8 Correct 6 ms 37384 KB Output is correct
9 Correct 0 ms 37384 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 37384 KB Output is correct
2 Runtime error 63 ms 37404 KB Execution killed because of forbidden syscall writev (20)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 216 ms 37384 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -