oj.uz

Submission #6068

# Submission time Handle Problem Language Result Execution time Memory
6068 2014-06-19T05:08:49 Z ainta 우호 조약 체결 (JOI14_friends) C++
0 / 100
 132 ms 14868 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#define N_ 100010
using namespace std;
int n, m, C[N_], par[N_];
long long C2[N_];
vector<int>E[N_], F[N_];
bool v[N_];
int SCC[N_], ord[N_], cnt;
int find(int a)
{
	if(a==par[a])return a;
	return par[a] = find(par[a]);
}
void DFS(int a)
{
	v[a] = true;
	int i;
	for(i=0;i<E[a].size();i++){
		if(!v[E[a][i]]){
			DFS(E[a][i]);
		}
	}
	ord[++cnt] = a;
}
void DFS2(int a)
{
	int i;
	C[cnt]++;
	SCC[a] = cnt;
	for(i=0;i<F[a].size();i++){
		if(!SCC[F[a][i]]){
			DFS2(F[a][i]);
		}
	}
}
void Merge(int a, int b){
	int x = find(a), y = find(b);
	if(x != y){
		par[y] = x;
		C[x] += C[y];
		C2[x] = (long long)C[x]*(C[x]-1);
	}
}
int main()
{
	int i, j, a, b;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&a,&b);
		E[a].push_back(b);
		F[b].push_back(a);
	}
	for(i=1;i<=n;i++){
		if(!v[i]){
			DFS(i);
		}
	}
	cnt = 0;
	for(i=n;i>=1;i--){
		if(!SCC[ord[i]]){
			cnt++;
			DFS2(ord[i]);
		}
	}
	for(i=1;i<=n;i++)F[i].clear();
	for(i=1;i<=n;i++){
		for(j=0;j<E[i].size();j++){
			if(SCC[i] != SCC[E[i][j]]){
				F[SCC[i]].push_back(SCC[E[i][j]]);
			}
			else{
				C2[SCC[i]]++;
			}
		}
	}
	for(i=1;i<=cnt;i++)par[i]=i;
	long long Res = 0;
	for(i=1;i<=cnt;i++){
		a=find(i);
		if(C[a] <C2[a])C2[a] = (long long)C[a]*(C[a]-1);
		for(j=0;j<F[i].size();j++){
			if(C[a] == 1 && j){
				Merge(F[a][j-1],F[a][j]);
			}
			if(C[a] == 1) Res++;
			if(C[a] != 1) Merge(a,F[a][j]);
		}
	}
	for(i=1;i<=cnt;i++){
		if(i == find(i)){
			Res += C2[i];
		}
	}
	printf("%lld\n",Res);
}

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 8468 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10584 KB Output is correct
2 Runtime error 132 ms 14868 KB SIGSEGV Segmentation fault
3 Halted 0 ms 0 KB -