oj.uz

답안 #3302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3302 2013-08-30T11:13:09 Z The_KMJ_God 두 섬간의 연결 (kriii1_2) C++
1 / 1
 48 ms 3432 KB 
// Problem 2. 두 섬간의 연결

#include<stdio.h>
int island[100010],tisland[100010];
long long v[100010][2],n;
int main()
{
	int i;
	int num,g1,g2;
	long long c1,c2;
	for(i=1;i<=100000;i++)
	{
		v[i+1][0]=v[i][0]+i;
		v[i+1][1]=v[i][1]+v[i+1][0];
		tisland[i]=i;
	}
	c1=0;
	c2=0;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d",&num);
		g1=num;
		g2=num+1;
		for(;;)
		{
			if(tisland[g1]==g1)
				break;
			g1=tisland[g1];
		}
		for(;;)
		{
			if(tisland[g2]==g2)
				break;
			g2=tisland[g2];
		}

		if(island[g1]==0&&island[g2]==0)
		{
			island[g1]=2;
			tisland[g2]=g1;
			c1+=1;
			c2+=1;
		}
		else if(island[g1]==0&&island[g2]!=0)
		{
			island[g1]=island[g2]+1;
			c1-=v[island[g2]][0];
			c2-=v[island[g2]][1];
			c1+=v[island[g1]][0];
			c2+=v[island[g1]][1];
			tisland[g2]=g1;
		}
		else if(island[g1]!=0&&island[g2]==0)
		{
			c1-=v[island[g1]][0];
			c2-=v[island[g1]][1];
			island[g1]++;
			c1+=v[island[g1]][0];
			c2+=v[island[g1]][1];
			tisland[g2]=g1;
		}
		else
		{
			c1-=v[island[g1]][0];
			c2-=v[island[g1]][1];
			c1-=v[island[g2]][0];
			c2-=v[island[g2]][1];
			island[g1]+=island[g2];
			c1+=v[island[g1]][0];
			c2+=v[island[g1]][1];
			tisland[g2]=g1;
		}
		printf("%lld %lld\n",c1,c2);
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 3432 KB Output is correct
2 Correct 40 ms 3432 KB Output is correct
3 Correct 40 ms 3432 KB Output is correct
4 Correct 44 ms 3432 KB Output is correct
5 Correct 40 ms 3432 KB Output is correct
6 Correct 44 ms 3432 KB Output is correct