oj.uz

답안 #12941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12941 2015-01-21T06:22:34 Z model_code 스파이 (JOI13_spy) C++
100 / 100
 312 ms 32424 KB 
#include <cstdio>
#include <algorithm>
#define MAXN 2000
#define MAXN2 4000
#define MAXM 500000
using namespace std;
int N,M;
int Pa,Qa;
int Rb,Sb;
int parenti[MAXN];
int parentj[MAXN];
int shachoi;
int shachoj;
int cnt[MAXN][MAXN];
int memo[MAXN][MAXN];

int memo_dp(int j,int i){
	if(memo[j][i]!=-1){return memo[j][i];}
	memo[j][i]=cnt[j][i];
	if(j!=shachoj){memo[j][i]+=memo_dp(parentj[j],i);}
	if(i!=shachoi){memo[j][i]+=memo_dp(j,parenti[i]);}
	if(j!=shachoj&&i!=shachoi){memo[j][i]-=memo_dp(parentj[j],parenti[i]);}
	return memo[j][i];
}
int main(){
	scanf("%d %d\n",&N,&M);
	for(int a=0;a<N;a++){
		scanf("%d %d\n",&Pa,&Qa);
		if(Pa!=0){
			Pa--;
			parentj[a]=Pa;
		}else{shachoj=a;}
		if(Qa!=0){
			Qa--;
			parenti[a]=Qa;
		}else{shachoi=a;}
		fill(memo[a],memo[a]+N,-1);
	}
	for(int b=0;b<M;b++){
		scanf("%d %d",&Rb,&Sb);
		Rb--;Sb--;
		cnt[Rb][Sb]+=1;
	}
	
	for(int i=0;i<N;i++){
		printf("%d\n",memo_dp(i,i));
	}
	
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 32392 KB Output is correct
2 Correct 136 ms 32424 KB Output is correct
3 Correct 4 ms 32352 KB Output is correct
4 Correct 0 ms 32352 KB Output is correct
5 Correct 4 ms 32352 KB Output is correct
6 Correct 4 ms 32352 KB Output is correct
7 Correct 108 ms 32352 KB Output is correct
8 Correct 20 ms 32352 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 32372 KB Output is correct
2 Correct 256 ms 32372 KB Output is correct
3 Correct 120 ms 32352 KB Output is correct
4 Correct 132 ms 32352 KB Output is correct
5 Correct 144 ms 32352 KB Output is correct
6 Correct 96 ms 32352 KB Output is correct
7 Correct 312 ms 32352 KB Output is correct
8 Correct 176 ms 32352 KB Output is correct