oj.uz

Submission #34014

# Submission time Handle Problem Language Result Execution time Memory
34014 2017-11-06T05:32:26 Z Dat160601 스파이 (JOI13_spy) C++14
100 / 100
 816 ms 65000 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 64868 KB Output is correct
2 Correct 0 ms 64868 KB Output is correct
3 Correct 3 ms 64868 KB Output is correct
4 Correct 0 ms 64868 KB Output is correct
5 Correct 3 ms 64868 KB Output is correct
6 Correct 3 ms 64868 KB Output is correct
7 Correct 3 ms 64868 KB Output is correct
8 Correct 0 ms 64868 KB Output is correct
9 Correct 0 ms 64868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 65000 KB Output is correct
2 Correct 489 ms 65000 KB Output is correct
3 Correct 499 ms 64868 KB Output is correct
4 Correct 493 ms 64868 KB Output is correct
5 Correct 473 ms 65000 KB Output is correct
6 Correct 446 ms 65000 KB Output is correct
7 Correct 446 ms 65000 KB Output is correct
8 Correct 476 ms 65000 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 65000 KB Output is correct
2 Correct 783 ms 65000 KB Output is correct
3 Correct 769 ms 64868 KB Output is correct
4 Correct 673 ms 64868 KB Output is correct
5 Correct 796 ms 65000 KB Output is correct
6 Correct 743 ms 65000 KB Output is correct
7 Correct 816 ms 65000 KB Output is correct
8 Correct 796 ms 65000 KB Output is correct