답안 #6070 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6070	2014-06-19T05:15:18 Z	ainta	우호 조약 체결 (JOI14_friends)	C++	100 / 100	172 ms	17544 KB

friends

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #6070

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 30.0 / 30.0

Subtask #3 65.0 / 65.0

Subtask #1
5.0 / 5.0

Subtask #2
30.0 / 30.0

Subtask #3
65.0 / 65.0