Submission #3313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3313	2013-08-30T11:34:32 Z	mjy0503	두 섬간의 연결 (kriii1_2)	C++	1 / 1	48 ms	2260 KB

2

#include <stdio.h>
long long print[2],cnt[100001];
int team[100001];
long long fir(long long a){
	return a*(a-1)/2;
}
long long sec(long long a){
	return (a-1)*a*(a+1)/6;
}
int main(){
	int n,i,a,j;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		team[i]=i;
		cnt[i]=1;
	}
	for(i=0;i<n-1;i++){
		scanf("%d",&a);
		print[0]-=fir(cnt[a]);
		print[0]-=fir(cnt[team[a-1]]);
		print[1]-=sec(cnt[a]);
		print[1]-=sec(cnt[team[a-1]]);
		for(j=a;j<n;j++){
			if(team[j]!=a) break;
			team[j]=team[a-1];
			cnt[team[a-1]]++;
		}
		print[0]+=fir(cnt[team[a-1]]);
		print[1]+=sec(cnt[team[a-1]]);
		printf("%lld %lld\n",print[0],print[1]);
	}
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	2260 KB	Output is correct
2	Correct	40 ms	2260 KB	Output is correct
3	Correct	48 ms	2260 KB	Output is correct
4	Correct	44 ms	2260 KB	Output is correct
5	Correct	40 ms	2260 KB	Output is correct
6	Correct	40 ms	2260 KB	Output is correct