답안 #3313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3313 2013-08-30T11:34:32 Z mjy0503 두 섬간의 연결 (kriii1_2) C++
1 / 1
48 ms 2260 KB
#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;
}
# 결과 실행 시간 메모리 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