oj.uz

Submission #6070

# Submission time Handle Problem Language Result Execution time Memory
6070 2014-06-19T05:15:18 Z ainta 우호 조약 체결 (JOI14_friends) C++
100 / 100
 172 ms 17544 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[i][j-1],F[i][j]);
			}
			if(C[a] == 1) Res++;
			if(C[a] != 1) Merge(i,F[i][j]);
		}
	}
	for(i=1;i<=cnt;i++){
		if(i == find(i)){
			Res += C2[i];
		}
	}
	printf("%lld\n",Res);
}

Subtask #1
5.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 Correct 0 ms 8340 KB Output is correct
5 Correct 0 ms 8340 KB Output is correct
6 Correct 0 ms 8340 KB Output is correct
7 Correct 0 ms 8340 KB Output is correct
8 Correct 0 ms 8340 KB Output is correct
9 Correct 0 ms 8340 KB Output is correct
10 Correct 4 ms 8340 KB Output is correct
11 Correct 0 ms 8340 KB Output is correct
12 Correct 0 ms 8340 KB Output is correct
13 Correct 0 ms 8340 KB Output is correct
14 Correct 0 ms 8340 KB Output is correct
15 Correct 0 ms 8340 KB Output is correct
16 Correct 0 ms 8340 KB Output is correct
17 Correct 0 ms 8340 KB Output is correct
18 Correct 0 ms 8340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8472 KB Output is correct
2 Correct 4 ms 8472 KB Output is correct
3 Correct 4 ms 8736 KB Output is correct
4 Correct 40 ms 10344 KB Output is correct
5 Correct 44 ms 9808 KB Output is correct
6 Correct 68 ms 11140 KB Output is correct
7 Correct 4 ms 8340 KB Output is correct
8 Correct 8 ms 8472 KB Output is correct
9 Correct 4 ms 8736 KB Output is correct
10 Correct 16 ms 9140 KB Output is correct
11 Correct 64 ms 11140 KB Output is correct
12 Correct 8 ms 8604 KB Output is correct
13 Correct 0 ms 8472 KB Output is correct
14 Correct 0 ms 8472 KB Output is correct
15 Correct 8 ms 8604 KB Output is correct
16 Correct 16 ms 8868 KB Output is correct
17 Correct 68 ms 11124 KB Output is correct
18 Correct 0 ms 8632 KB Output is correct
19 Correct 0 ms 8604 KB Output is correct
20 Correct 64 ms 11136 KB Output is correct
21 Correct 0 ms 8604 KB Output is correct
22 Correct 4 ms 8604 KB Output is correct
23 Correct 8 ms 8604 KB Output is correct
24 Correct 0 ms 8472 KB Output is correct
25 Correct 0 ms 8604 KB Output is correct
26 Correct 0 ms 8472 KB Output is correct
27 Correct 0 ms 8640 KB Output is correct
28 Correct 0 ms 8604 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10584 KB Output is correct
2 Correct 152 ms 14872 KB Output is correct
3 Correct 164 ms 14736 KB Output is correct
4 Correct 88 ms 12960 KB Output is correct
5 Correct 36 ms 11508 KB Output is correct
6 Correct 124 ms 13064 KB Output is correct
7 Correct 116 ms 14160 KB Output is correct
8 Correct 108 ms 14148 KB Output is correct
9 Correct 64 ms 12960 KB Output is correct
10 Correct 100 ms 13492 KB Output is correct
11 Correct 144 ms 14912 KB Output is correct
12 Correct 156 ms 15476 KB Output is correct
13 Correct 88 ms 14544 KB Output is correct
14 Correct 80 ms 11404 KB Output is correct
15 Correct 44 ms 11508 KB Output is correct
16 Correct 0 ms 8604 KB Output is correct
17 Correct 8 ms 8340 KB Output is correct
18 Correct 172 ms 14256 KB Output is correct
19 Correct 164 ms 14244 KB Output is correct
20 Correct 88 ms 12564 KB Output is correct
21 Correct 40 ms 11244 KB Output is correct
22 Correct 0 ms 8340 KB Output is correct
23 Correct 44 ms 9792 KB Output is correct
24 Correct 88 ms 12480 KB Output is correct
25 Correct 76 ms 17544 KB Output is correct
26 Correct 72 ms 17544 KB Output is correct
27 Correct 160 ms 16012 KB Output is correct
28 Correct 84 ms 13648 KB Output is correct
29 Correct 80 ms 13600 KB Output is correct
30 Correct 156 ms 14984 KB Output is correct
31 Correct 72 ms 13224 KB Output is correct
32 Correct 56 ms 14544 KB Output is correct
33 Correct 76 ms 14544 KB Output is correct
34 Correct 76 ms 13092 KB Output is correct
35 Correct 80 ms 17544 KB Output is correct
36 Correct 72 ms 17544 KB Output is correct
37 Correct 88 ms 13644 KB Output is correct