oj.uz

Submission #62635

# Submission time Handle Problem Language Result Execution time Memory
62635 2018-07-29T14:41:15 Z IvanC Duathlon (APIO18_duathlon) C++17
31 / 100
 352 ms 73140 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -