Submission #26413

#	Time	Username	Problem	Language	Result	Execution time	Memory
26413		zscoder	스파이 (JOI13_spy)	C++14	10 / 100	196 ms	37404 KiB

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70