oj.uz

Submission #58375

# Submission time Handle Problem Language Result Execution time Memory
58375 2018-07-17T15:20:03 Z IvanC Duathlon (APIO18_duathlon) C++17
31 / 100
 285 ms 49844 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2*1e5 + 10;

vector<int> grafo[MAXN],tree[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]]++;
	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
		//trincas_total += 1LL*v2*v1*(v1 - 1); // dentro-dentro-fora
		//printf("V %d U %d %lld %lld %lld\n",v,u,1LL*v1*v2*v3,1LL*v2*v1*(v1 - 1),1LL*v2*v1*(v1 - 1));
	}
	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*v2*v1*(v1 - 1); // dentro-dentro-fora
	trincas_total += 1LL*(v1)*(v1 - 1)*(v1 - 2); // dentro-dentro-dentro
	//printf("V %d U Resto %lld %lld %lld\n",v,1LL*v1*v2*v3,1LL*v2*v1*(v1 - 1),1LL*v2*v1*(v1 - 1));
	//printf("V escolhe 3 %d %lld\n",v,1LL*v1*(v1-1)*(v1 - 2));
}

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:85: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:87: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 12 ms 9720 KB Output is correct
2 Correct 11 ms 9968 KB Output is correct
3 Correct 13 ms 9968 KB Output is correct
4 Correct 14 ms 9992 KB Output is correct
5 Correct 13 ms 9992 KB Output is correct
6 Correct 11 ms 9992 KB Output is correct
7 Incorrect 11 ms 9992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 11 ms 9968 KB Output is correct
3 Correct 13 ms 9968 KB Output is correct
4 Correct 14 ms 9992 KB Output is correct
5 Correct 13 ms 9992 KB Output is correct
6 Correct 11 ms 9992 KB Output is correct
7 Incorrect 11 ms 9992 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 191 ms 24468 KB Output is correct
2 Correct 179 ms 25800 KB Output is correct
3 Correct 229 ms 25800 KB Output is correct
4 Correct 216 ms 27728 KB Output is correct
5 Correct 218 ms 27728 KB Output is correct
6 Correct 222 ms 28176 KB Output is correct
7 Correct 192 ms 28648 KB Output is correct
8 Correct 281 ms 30408 KB Output is correct
9 Correct 182 ms 30408 KB Output is correct
10 Correct 189 ms 31848 KB Output is correct
11 Correct 131 ms 31848 KB Output is correct
12 Correct 132 ms 32272 KB Output is correct
13 Correct 116 ms 33312 KB Output is correct
14 Correct 138 ms 34028 KB Output is correct
15 Correct 108 ms 34572 KB Output is correct
16 Correct 113 ms 34896 KB Output is correct
17 Correct 22 ms 34896 KB Output is correct
18 Correct 20 ms 34896 KB Output is correct
19 Correct 19 ms 34896 KB Output is correct
20 Correct 21 ms 34896 KB Output is correct
21 Correct 17 ms 34896 KB Output is correct
22 Correct 16 ms 34896 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 39612 KB Output is correct
2 Correct 177 ms 40952 KB Output is correct
3 Correct 229 ms 41948 KB Output is correct
4 Correct 200 ms 43232 KB Output is correct
5 Correct 209 ms 44620 KB Output is correct
6 Correct 258 ms 49844 KB Output is correct
7 Correct 227 ms 49844 KB Output is correct
8 Correct 285 ms 49844 KB Output is correct
9 Correct 189 ms 49844 KB Output is correct
10 Correct 208 ms 49844 KB Output is correct
11 Correct 186 ms 49844 KB Output is correct
12 Correct 167 ms 49844 KB Output is correct
13 Correct 260 ms 49844 KB Output is correct
14 Correct 162 ms 49844 KB Output is correct
15 Correct 159 ms 49844 KB Output is correct
16 Correct 114 ms 49844 KB Output is correct
17 Correct 89 ms 49844 KB Output is correct
18 Correct 97 ms 49844 KB Output is correct
19 Correct 134 ms 49844 KB Output is correct
20 Correct 154 ms 49844 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49844 KB Output is correct
2 Correct 13 ms 49844 KB Output is correct
3 Incorrect 14 ms 49844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 49844 KB Output is correct
2 Correct 211 ms 49844 KB Output is correct
3 Incorrect 253 ms 49844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 11 ms 9968 KB Output is correct
3 Correct 13 ms 9968 KB Output is correct
4 Correct 14 ms 9992 KB Output is correct
5 Correct 13 ms 9992 KB Output is correct
6 Correct 11 ms 9992 KB Output is correct
7 Incorrect 11 ms 9992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 11 ms 9968 KB Output is correct
3 Correct 13 ms 9968 KB Output is correct
4 Correct 14 ms 9992 KB Output is correct
5 Correct 13 ms 9992 KB Output is correct
6 Correct 11 ms 9992 KB Output is correct
7 Incorrect 11 ms 9992 KB Output isn't correct
8 Halted 0 ms 0 KB -