답안 #62635 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62635	2018-07-29T14:41:15 Z	IvanC	철인 이종 경기 (APIO18_duathlon)	C++17	31 / 100	352 ms	73140 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3*1e5 + 10;

long long resposta;
vector<int> grafo[MAXN],tree[MAXN],pilha;
int N,M,low[MAXN],num[MAXN],dfsCount,e1[MAXN],e2[MAXN],compIdx;
int component_size,subtreeSz[MAXN],ownSize[MAXN];

long long escolhe3(int x){
	return 1LL*x*(x-1)*(x-2);
}

void get_bcc(int i){
	vector<int> membros;
	while(!pilha.empty()){
		int j = pilha.back();
		pilha.pop_back();
		membros.push_back(e1[j]);
		membros.push_back(e2[j]);
		if(j == i) break;
	}
	sort(membros.begin(),membros.end());
	membros.erase(unique(membros.begin(),membros.end()),membros.end());
	compIdx++;
	for(int v : membros){
		tree[v].push_back(compIdx);
		tree[compIdx].push_back(v);
	}
	resposta += escolhe3(membros.size());
}

void dfs_tarjan(int v,int p){

	component_size++;

	num[v] = ++dfsCount;
	low[v] = num[v];

	for(int i : grafo[v]){
		
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);

		if(u == p) continue;

		if(num[u] == 0){
			pilha.push_back(i);
			dfs_tarjan(u,v);
			if(num[v] <= low[u]){
				get_bcc(i);
			}
			low[v] = min(low[v],low[u]);
		}
		else if(num[u] < num[v]){
			low[v] = min(low[v],num[u]);
		}

	}

}

void dfs_combinatorics(int v,int p){

	ownSize[v] = (v <= N);
	subtreeSz[v] = ownSize[v];

	for(int u : tree[v]){
		if(u == p) continue;
		dfs_combinatorics(u,v);
		subtreeSz[v] += subtreeSz[u];
	}

	for(int u : tree[v]){
		if(u == p) continue;
		int c1 = subtreeSz[u];
		int c2 = ownSize[v];
		int c3 = (component_size - c1 - c2);
		resposta += 1LL*c1*c2*c3;
	}

	int c1 = (component_size - subtreeSz[v]);
	int c2 = ownSize[v];
	int c3 = (subtreeSz[v] - ownSize[v]);
	resposta += 1LL*c1*c2*c3;

	if(v > N){

		int cycle_size = (int)tree[v].size();
		int other_size = component_size - cycle_size;
		resposta += 2LL*(cycle_size - 1)*(cycle_size - 2)*other_size;

	}

}

int main(){

	scanf("%d %d",&N,&M);
	compIdx = N;
	for(int i = 1;i<=M;i++){
		scanf("%d %d",&e1[i],&e2[i]);
		grafo[e1[i]].push_back(i);
		grafo[e2[i]].push_back(i);
	}

	for(int i = 1;i<=N;i++){
		if(num[i] != 0) continue;
		component_size = 0;
		dfs_tarjan(i,-1);
		dfs_combinatorics(i,-1);
	}

	printf("%lld\n",resposta);

	return 0;

}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&e1[i],&e2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14432 KB	Output is correct
2	Correct	17 ms	14696 KB	Output is correct
3	Correct	16 ms	14696 KB	Output is correct
4	Correct	25 ms	14704 KB	Output is correct
5	Correct	21 ms	14704 KB	Output is correct
6	Correct	16 ms	14776 KB	Output is correct
7	Incorrect	16 ms	14776 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14432 KB	Output is correct
2	Correct	17 ms	14696 KB	Output is correct
3	Correct	16 ms	14696 KB	Output is correct
4	Correct	25 ms	14704 KB	Output is correct
5	Correct	21 ms	14704 KB	Output is correct
6	Correct	16 ms	14776 KB	Output is correct
7	Incorrect	16 ms	14776 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	34712 KB	Output is correct
2	Correct	224 ms	36100 KB	Output is correct
3	Correct	236 ms	36100 KB	Output is correct
4	Correct	264 ms	37652 KB	Output is correct
5	Correct	226 ms	37652 KB	Output is correct
6	Correct	295 ms	38744 KB	Output is correct
7	Correct	228 ms	38744 KB	Output is correct
8	Correct	300 ms	39700 KB	Output is correct
9	Correct	231 ms	39700 KB	Output is correct
10	Correct	281 ms	40404 KB	Output is correct
11	Correct	205 ms	40404 KB	Output is correct
12	Correct	184 ms	40404 KB	Output is correct
13	Correct	199 ms	40404 KB	Output is correct
14	Correct	192 ms	41116 KB	Output is correct
15	Correct	165 ms	41116 KB	Output is correct
16	Correct	158 ms	41272 KB	Output is correct
17	Correct	20 ms	41272 KB	Output is correct
18	Correct	21 ms	41272 KB	Output is correct
19	Correct	20 ms	41272 KB	Output is correct
20	Correct	20 ms	41272 KB	Output is correct
21	Correct	20 ms	41272 KB	Output is correct
22	Correct	20 ms	41272 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	41272 KB	Output is correct
2	Correct	17 ms	41272 KB	Output is correct
3	Correct	18 ms	41272 KB	Output is correct
4	Correct	18 ms	41272 KB	Output is correct
5	Correct	19 ms	41272 KB	Output is correct
6	Correct	18 ms	41272 KB	Output is correct
7	Correct	19 ms	41272 KB	Output is correct
8	Correct	21 ms	41272 KB	Output is correct
9	Correct	23 ms	41272 KB	Output is correct
10	Correct	21 ms	41272 KB	Output is correct
11	Correct	20 ms	41272 KB	Output is correct
12	Correct	23 ms	41272 KB	Output is correct
13	Correct	21 ms	41272 KB	Output is correct
14	Correct	23 ms	41272 KB	Output is correct
15	Correct	19 ms	41272 KB	Output is correct
16	Correct	18 ms	41272 KB	Output is correct
17	Correct	21 ms	41272 KB	Output is correct
18	Correct	18 ms	41272 KB	Output is correct
19	Correct	17 ms	41272 KB	Output is correct
20	Correct	18 ms	41272 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	258 ms	47024 KB	Output is correct
2	Correct	297 ms	48396 KB	Output is correct
3	Correct	292 ms	49616 KB	Output is correct
4	Correct	262 ms	50744 KB	Output is correct
5	Correct	294 ms	52016 KB	Output is correct
6	Correct	297 ms	61892 KB	Output is correct
7	Correct	285 ms	61892 KB	Output is correct
8	Correct	352 ms	61892 KB	Output is correct
9	Correct	338 ms	61892 KB	Output is correct
10	Correct	272 ms	61892 KB	Output is correct
11	Correct	295 ms	61892 KB	Output is correct
12	Correct	261 ms	61892 KB	Output is correct
13	Correct	226 ms	61996 KB	Output is correct
14	Correct	260 ms	62664 KB	Output is correct
15	Correct	194 ms	62788 KB	Output is correct
16	Correct	124 ms	62788 KB	Output is correct
17	Correct	167 ms	66712 KB	Output is correct
18	Correct	209 ms	68008 KB	Output is correct
19	Correct	212 ms	69268 KB	Output is correct
20	Correct	236 ms	70384 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	70384 KB	Output is correct
2	Correct	22 ms	70384 KB	Output is correct
3	Incorrect	22 ms	70384 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	295 ms	71020 KB	Output is correct
2	Correct	291 ms	72136 KB	Output is correct
3	Incorrect	293 ms	73140 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14432 KB	Output is correct
2	Correct	17 ms	14696 KB	Output is correct
3	Correct	16 ms	14696 KB	Output is correct
4	Correct	25 ms	14704 KB	Output is correct
5	Correct	21 ms	14704 KB	Output is correct
6	Correct	16 ms	14776 KB	Output is correct
7	Incorrect	16 ms	14776 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14432 KB	Output is correct
2	Correct	17 ms	14696 KB	Output is correct
3	Correct	16 ms	14696 KB	Output is correct
4	Correct	25 ms	14704 KB	Output is correct
5	Correct	21 ms	14704 KB	Output is correct
6	Correct	16 ms	14776 KB	Output is correct
7	Incorrect	16 ms	14776 KB	Output isn't correct
8	Halted	0 ms	0 KB	-