Submission #26413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26413	2017-06-30T04:41:13 Z	zscoder	스파이 (JOI13_spy)	C++14	10 / 100	196 ms	37404 KB

spy

#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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 ms	37384 KB	Output is correct
8	Correct	0 ms	37384 KB	Output is correct
9	Correct	6 ms	37384 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	37388 KB	Output is correct
2	Runtime error	56 ms	37404 KB	Execution killed because of forbidden syscall writev (20)
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	196 ms	37384 KB	Execution killed because of forbidden syscall writev (20)
2	Halted	0 ms	0 KB	-