Submission #14712

#	Time	Username	Problem	Language	Result	Execution time	Memory
14712		gs13068	우호 조약 체결 (JOI14_friends)	C++98	0 / 100	74 ms	5736 KiB

friends

#include<cstdio>
#include<vector>

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);p[x]=y;q[y]+=q[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;
	}
    for(i=1;i<=n;i++)for(j=1;j<a[i].size();j++)com(a[i][j],a[i][0]);
    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: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65