oj.uz

Submission #14712

# Submission time Handle Problem Language Result Execution time Memory
14712 2015-06-11T09:28:13 Z gs13068 우호 조약 체결 (JOI14_friends) C++
0 / 100
 74 ms 5736 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4680 KB Output is correct
2 Correct 0 ms 4680 KB Output is correct
3 Correct 0 ms 4680 KB Output is correct
4 Incorrect 0 ms 4680 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 0 ms 4680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

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