oj.uz

Submission #59336

# Submission time Handle Problem Language Result Execution time Memory
59336 2018-07-21T14:53:56 Z IvanC Duathlon (APIO18_duathlon) C++17
66 / 100
 406 ms 36420 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 2*1e5 + 10;
 
vector<int> grafo[MAXN],tree[MAXN],meucomponente[MAXN];
int e1[MAXN],e2[MAXN],e3[MAXN],jafoi[MAXN],N,M;
int compSz[MAXN],subtreeSz[MAXN],compId[MAXN],lastComp;
int low[MAXN],num[MAXN],dfsCount,total_componente;
ll trincas_total;
 
void dfs1(int v,int aresta){
	total_componente++;
	num[v] = low[v] = ++dfsCount;
	for(int i : grafo[v]){
		if(i == aresta) continue;
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(num[u] == 0){
			dfs1(u,i);
			if(num[v] < low[u]){
				e3[i] = 1;
			}
			low[v] = min(low[v],low[u]);
		}
		else{
			low[v] = min(low[v],num[u]);
		}
	}
}
 
void dfs2(int v,int aresta){
	if(jafoi[v]) return;
	jafoi[v] = 1;
	compSz[compId[v]]++;
	meucomponente[compId[v]].push_back(v);
	for(int i : grafo[v]){
		if(i == aresta) continue;
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(num[v] >= num[u] ) continue;
		if(e3[i] == 1){
			lastComp++;
			compId[u] = lastComp;
			tree[compId[v]].push_back(compId[u]);
			tree[compId[u]].push_back(compId[v]);
			dfs2(u,i);
		}
		else{
			compId[u] = compId[v];
			dfs2(u,i);
		}
	}
}
 
void dfs3(int v,int p){
	subtreeSz[v] = compSz[v];
	for(int u : tree[v]){
		if(u == p) continue;
		dfs3(u,v);
		subtreeSz[v] += subtreeSz[u];
	}
	for(int u : tree[v]){
		if(u == p) continue;
		int v1 = compSz[v]; // dentro
		int v2 = subtreeSz[u]; // fora, esta subtree
		int v3 = total_componente - v1 - v2; // fora, outras subtrees
		trincas_total += 1LL*v1*v2*v3; // fora-dentro-fora
		trincas_total += 2LL*v2*(v1 - 1)*(v1 - 1); // fora-dentro-dentro
	}
	int v1 = compSz[v]; // dentro
	int v2 = (total_componente - subtreeSz[v]); // fora, esta subtree
	int v3 = (subtreeSz[v] - compSz[v]);// fora, outras subtrees
	trincas_total += 1LL*v1*v2*v3; // fora-dentro-fora
	trincas_total += 2LL*v2*(v1 - 1)*(v1 - 1); // fora-dentro-dentro
	trincas_total += 1LL*(v1)*(v1 - 1)*(v1 - 2); // dentro-dentro-dentro
	
	for(int k : meucomponente[v]){
		
		vector<int> tamanhos;
		int filhos = 0;
		
		for(int i : grafo[k]){
			int u = (e1[i] != k) ? (e1[i]) : (e2[i]);
			int l = compId[u];
			if(l == v) continue;
			if(l == p){
				tamanhos.push_back(total_componente - subtreeSz[v]);
			}
			else{
				tamanhos.push_back(subtreeSz[l]);
			}
		}
		
		for(int valor : tamanhos) filhos += valor;
		
		for(int valor : tamanhos){
			trincas_total -= 1LL*(valor)*(filhos - valor)*(v1 - 1);
		}
		
	}
	
}
 
int main(){
	
	scanf("%d %d",&N,&M);
	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;
		total_componente = 0;
		dfs1(i,-1);
		lastComp++;
		compId[i] = lastComp;
		dfs2(i,-1);
		dfs3(compId[i],-1);
	}
	
	printf("%lld\n",trincas_total);
	
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:107: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:109: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 14 ms 14456 KB Output is correct
2 Correct 17 ms 14540 KB Output is correct
3 Correct 17 ms 14616 KB Output is correct
4 Correct 17 ms 14616 KB Output is correct
5 Correct 20 ms 14616 KB Output is correct
6 Correct 18 ms 14616 KB Output is correct
7 Correct 19 ms 14644 KB Output is correct
8 Incorrect 15 ms 14720 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 17 ms 14540 KB Output is correct
3 Correct 17 ms 14616 KB Output is correct
4 Correct 17 ms 14616 KB Output is correct
5 Correct 20 ms 14616 KB Output is correct
6 Correct 18 ms 14616 KB Output is correct
7 Correct 19 ms 14644 KB Output is correct
8 Incorrect 15 ms 14720 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 28576 KB Output is correct
2 Correct 252 ms 28576 KB Output is correct
3 Correct 303 ms 30696 KB Output is correct
4 Correct 290 ms 30696 KB Output is correct
5 Correct 242 ms 30696 KB Output is correct
6 Correct 352 ms 30696 KB Output is correct
7 Correct 313 ms 30696 KB Output is correct
8 Correct 293 ms 30696 KB Output is correct
9 Correct 326 ms 30696 KB Output is correct
10 Correct 328 ms 30696 KB Output is correct
11 Correct 188 ms 30696 KB Output is correct
12 Correct 211 ms 30696 KB Output is correct
13 Correct 176 ms 30696 KB Output is correct
14 Correct 189 ms 30696 KB Output is correct
15 Correct 182 ms 30696 KB Output is correct
16 Correct 178 ms 30696 KB Output is correct
17 Correct 36 ms 30696 KB Output is correct
18 Correct 34 ms 30696 KB Output is correct
19 Correct 32 ms 30696 KB Output is correct
20 Correct 32 ms 30696 KB Output is correct
21 Correct 33 ms 30696 KB Output is correct
22 Correct 33 ms 30696 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30696 KB Output is correct
2 Correct 19 ms 30696 KB Output is correct
3 Correct 20 ms 30696 KB Output is correct
4 Correct 20 ms 30696 KB Output is correct
5 Correct 18 ms 30696 KB Output is correct
6 Correct 22 ms 30696 KB Output is correct
7 Correct 18 ms 30696 KB Output is correct
8 Correct 18 ms 30696 KB Output is correct
9 Correct 22 ms 30696 KB Output is correct
10 Correct 18 ms 30696 KB Output is correct
11 Correct 19 ms 30696 KB Output is correct
12 Correct 19 ms 30696 KB Output is correct
13 Correct 20 ms 30696 KB Output is correct
14 Correct 18 ms 30696 KB Output is correct
15 Correct 18 ms 30696 KB Output is correct
16 Correct 17 ms 30696 KB Output is correct
17 Correct 15 ms 30696 KB Output is correct
18 Correct 16 ms 30696 KB Output is correct
19 Correct 16 ms 30696 KB Output is correct
20 Correct 18 ms 30696 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 30696 KB Output is correct
2 Correct 336 ms 30696 KB Output is correct
3 Correct 327 ms 30696 KB Output is correct
4 Correct 342 ms 30696 KB Output is correct
5 Correct 351 ms 30696 KB Output is correct
6 Correct 384 ms 36420 KB Output is correct
7 Correct 395 ms 36420 KB Output is correct
8 Correct 406 ms 36420 KB Output is correct
9 Correct 334 ms 36420 KB Output is correct
10 Correct 364 ms 36420 KB Output is correct
11 Correct 362 ms 36420 KB Output is correct
12 Correct 357 ms 36420 KB Output is correct
13 Correct 329 ms 36420 KB Output is correct
14 Correct 204 ms 36420 KB Output is correct
15 Correct 201 ms 36420 KB Output is correct
16 Correct 120 ms 36420 KB Output is correct
17 Correct 130 ms 36420 KB Output is correct
18 Correct 145 ms 36420 KB Output is correct
19 Correct 176 ms 36420 KB Output is correct
20 Correct 227 ms 36420 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36420 KB Output is correct
2 Correct 18 ms 36420 KB Output is correct
3 Correct 16 ms 36420 KB Output is correct
4 Correct 22 ms 36420 KB Output is correct
5 Correct 18 ms 36420 KB Output is correct
6 Correct 19 ms 36420 KB Output is correct
7 Correct 16 ms 36420 KB Output is correct
8 Correct 16 ms 36420 KB Output is correct
9 Correct 16 ms 36420 KB Output is correct
10 Correct 15 ms 36420 KB Output is correct
11 Correct 18 ms 36420 KB Output is correct
12 Correct 19 ms 36420 KB Output is correct
13 Correct 17 ms 36420 KB Output is correct
14 Correct 20 ms 36420 KB Output is correct
15 Correct 17 ms 36420 KB Output is correct
16 Correct 16 ms 36420 KB Output is correct
17 Correct 18 ms 36420 KB Output is correct
18 Correct 15 ms 36420 KB Output is correct
19 Correct 16 ms 36420 KB Output is correct
20 Correct 19 ms 36420 KB Output is correct
21 Correct 17 ms 36420 KB Output is correct
22 Correct 15 ms 36420 KB Output is correct
23 Correct 16 ms 36420 KB Output is correct
24 Correct 21 ms 36420 KB Output is correct
25 Correct 18 ms 36420 KB Output is correct
26 Correct 17 ms 36420 KB Output is correct
27 Correct 16 ms 36420 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 36420 KB Output is correct
2 Correct 323 ms 36420 KB Output is correct
3 Correct 348 ms 36420 KB Output is correct
4 Correct 242 ms 36420 KB Output is correct
5 Correct 282 ms 36420 KB Output is correct
6 Correct 259 ms 36420 KB Output is correct
7 Correct 219 ms 36420 KB Output is correct
8 Correct 200 ms 36420 KB Output is correct
9 Correct 260 ms 36420 KB Output is correct
10 Correct 180 ms 36420 KB Output is correct
11 Correct 213 ms 36420 KB Output is correct
12 Correct 218 ms 36420 KB Output is correct
13 Correct 220 ms 36420 KB Output is correct
14 Correct 180 ms 36420 KB Output is correct
15 Correct 352 ms 36420 KB Output is correct
16 Correct 352 ms 36420 KB Output is correct
17 Correct 368 ms 36420 KB Output is correct
18 Correct 346 ms 36420 KB Output is correct
19 Correct 240 ms 36420 KB Output is correct
20 Correct 328 ms 36420 KB Output is correct
21 Correct 317 ms 36420 KB Output is correct
22 Correct 180 ms 36420 KB Output is correct
23 Correct 176 ms 36420 KB Output is correct
24 Correct 251 ms 36420 KB Output is correct
25 Correct 326 ms 36420 KB Output is correct
26 Correct 293 ms 36420 KB Output is correct
27 Correct 328 ms 36420 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 17 ms 14540 KB Output is correct
3 Correct 17 ms 14616 KB Output is correct
4 Correct 17 ms 14616 KB Output is correct
5 Correct 20 ms 14616 KB Output is correct
6 Correct 18 ms 14616 KB Output is correct
7 Correct 19 ms 14644 KB Output is correct
8 Incorrect 15 ms 14720 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 17 ms 14540 KB Output is correct
3 Correct 17 ms 14616 KB Output is correct
4 Correct 17 ms 14616 KB Output is correct
5 Correct 20 ms 14616 KB Output is correct
6 Correct 18 ms 14616 KB Output is correct
7 Correct 19 ms 14644 KB Output is correct
8 Incorrect 15 ms 14720 KB Output isn't correct
9 Halted 0 ms 0 KB -