Submission #34014

#	Time	Username	Problem	Language	Result	Execution time	Memory
34014		Dat160601	스파이 (JOI13_spy)	C++14	100 / 100	816 ms	65000 KiB

spy

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,u,v,vis[2007],root1,root2,cnt=0;
int st[2007],fs[2007];
int st2[2007],fs2[2007],dp[4007][4007];
vector < int > edge[2007],ed[2007];
void dfs1(int u){
	cnt++;
	st[u]=cnt;
	for(int i=0;i<(int)edge[u].size();i++){
		int v=edge[u][i];
		dfs1(v);
	}
	cnt++;
	fs[u]=cnt;
}
void dfs2(int u){
	cnt++;
	st2[u]=cnt;
	for(int i=0;i<(int)ed[u].size();i++){
		int v=ed[u][i];
		dfs2(v);
	}
	cnt++;
	fs2[u]=cnt;
}
int main(){
	//ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>u>>v;
		if(u==0){
			root1=i;
		}
		else edge[u].pb(i);
		if(v==0){
			root2=i;
		}
		else ed[v].pb(i);
	}
	dfs1(root1);
	cnt=0;
	dfs2(root2);
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		dp[st[u]][st2[v]]++;
		dp[st[u]][fs2[v]]--;
		dp[fs[u]][fs2[v]]++;
		dp[fs[u]][st2[v]]--;
	}
	int cur=0;
	for(int i=1;i<=2*n;i++){
		cur=0;
		for(int j=1;j<=2*n;j++){
			cur+=dp[j][i];
			dp[j][i]=cur;
		}
	}
	for(int i=1;i<=2*n;i++){
		cur=0;
		for(int j=1;j<=2*n;j++){
			cur+=dp[i][j];
			dp[i][j]=cur;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dp[st[i]][st2[i]]<<"\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70