Submission #14714

#	Time	Username	Problem	Language	Result	Execution time	Memory
14714		gs13068	우호 조약 체결 (JOI14_friends)	C++98	100 / 100	132 ms	12284 KiB

friends

#include<cstdio>
#include<vector>
#include<algorithm>

std::vector<int> a[111111];
int p[111111];
int q[111111];

int par(int x){return x==p[x]?x:p[x]=par(p[x]);}
void com(int x,int y)
{
	x=par(x);y=par(y);
	if(x==y)return;
	p[x]=y;q[y]+=q[x];
    int i;
    for(i=0;i<a[x].size();i++)com(a[x][i],y);
    for(i=0;i<a[y].size();i++)com(a[y][i],x);
}

int main()
{
	long long res;
	int i,j,n,m;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&i,&j);
		a[i].push_back(j);
	}
	for(i=1;i<=n;i++)
	{
		p[i]=i;
		q[i]=1;
		std::sort(a[i].begin(),a[i].end());
	}
    for(i=1;i<=n;i++)
	{
		if(!a[i].empty()&&binary_search(a[a[i][0]].begin(),a[a[i][0]].end(),i))com(a[i][0],i);
		for(j=1;j<a[i].size();j++)
		{
			com(a[i][j],a[i][0]);
			if(binary_search(a[a[i][j]].begin(),a[a[i][j]].end(),i))com(a[i][j],i);
		}
	}
    res=0;
    for(i=1;i<=n;i++)
	{
		if(i==p[i])res+=1LL*q[i]*(q[i]-1);
        for(j=0;j<a[i].size();j++)if(par(i)!=par(a[i][j]))res++;
	}
	printf("%lld\n",res);
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65