제출 #3302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3302		The_KMJ_God	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	48 ms	3432 KiB

2

// 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 / 1