oj.uz

Submission #14713

# Submission time Handle Problem Language Result Execution time Memory
14713 2015-06-11T09:36:52 Z gs13068 우호 조약 체결 (JOI14_friends) C++
0 / 100
 124 ms 7456 KB 
#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){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;
		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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4684 KB Output is correct
2 Correct 0 ms 4684 KB Output is correct
3 Correct 0 ms 4684 KB Output is correct
4 Incorrect 1 ms 4684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5740 KB Output is correct
2 Incorrect 124 ms 7456 KB Output isn't correct
3 Halted 0 ms 0 KB -