oj.uz

Submission #48872

# Submission time Handle Problem Language Result Execution time Memory
48872 2018-05-19T11:42:26 Z IvanC Duathlon (APIO18_duathlon) C++17
31 / 100
 263 ms 22888 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

const int MAXN = 1e5 + 10;


vector<int> grafo[MAXN],arvore[MAXN];
int N,M,e1[2*MAXN],e2[2*MAXN],isbridge[2*MAXN],num[MAXN],low[MAXN],dfsCount,treeComp,bridgeTreeId[MAXN],bridge_sz[MAXN],sz[MAXN],block[MAXN];
ll tot,comp_size;

void dfs_tarjan(int v,int p){
	num[v] = low[v] = ++dfsCount;
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? e1[idx] : e2[idx];
		if(u == p) continue;
		if(num[u] == 0){
			dfs_tarjan(u,v);
			if(low[u] > num[v]) isbridge[idx] = 1;
			low[v] = min(low[v],low[u]);
		}
		else{
			low[v] = min(low[v],num[u]);
		}
	}
}
void dfs_bridge(int v,int p,int compId){
	if(compId == -1) compId = ++treeComp;
	bridgeTreeId[v] = compId;
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? e1[idx] : e2[idx];
		if(u == p || bridgeTreeId[u]) continue;
		if(isbridge[idx]){
			dfs_bridge(u,v,-1);
			arvore[bridgeTreeId[v]].push_back(bridgeTreeId[u]);
			arvore[bridgeTreeId[u]].push_back(bridgeTreeId[v]);
		}
		else{
			dfs_bridge(u,v,compId);
		}
	}
}

void dfs_tree_1(int v,int p){
	block[v] = 1;
	sz[v] = bridge_sz[v];
	for(int u : arvore[v]){
		if(u == p) continue;
		dfs_tree_1(u,v);
		sz[v] += sz[u];
	}
}

void dfs_tree_2(int v,int p){
	tot += 1LL*(bridge_sz[v])*max(bridge_sz[v] - 1,0)*max(bridge_sz[v]-2,0);
	vector<int> filhos;
	for(int u : arvore[v]){
		if(u == p) continue;
		filhos.push_back(sz[u]);
		dfs_tree_2(u,v);
	}
	filhos.push_back(comp_size - sz[v]);
	for(int i = 0;i<filhos.size();i++){
		int sub_arvore = filhos[i];
		tot += 1LL*bridge_sz[v]*sub_arvore*(comp_size - sub_arvore - bridge_sz[v]);
		tot += 2LL*sub_arvore*(bridge_sz[v] - 1)*max(bridge_sz[v] - 2,0);
		tot += 2LL*sub_arvore*(bridge_sz[v] - 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){
			dfs_tarjan(i,-1);
			dfs_bridge(i,-1,-1);
		}
	}

	for(int i = 1;i<=N;i++) bridge_sz[bridgeTreeId[i]]++;

	for(int i = 1;i<=treeComp;i++){
		if(block[i]) continue;
		dfs_tree_1(i,-1);
		comp_size = sz[i];
		dfs_tree_2(i,-1);
	}

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

	return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs_tarjan(int, int)':
count_triplets.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs_bridge(int, int, int)':
count_triplets.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs_tree_2(int, int)':
count_triplets.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<filhos.size();i++){
                ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:76: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:79: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 6 ms 4956 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 5 ms 5220 KB Output is correct
5 Correct 5 ms 5220 KB Output is correct
6 Correct 5 ms 5220 KB Output is correct
7 Incorrect 6 ms 5220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4956 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 5 ms 5220 KB Output is correct
5 Correct 5 ms 5220 KB Output is correct
6 Correct 5 ms 5220 KB Output is correct
7 Incorrect 6 ms 5220 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 151 ms 18156 KB Output is correct
2 Correct 193 ms 18156 KB Output is correct
3 Correct 176 ms 18788 KB Output is correct
4 Correct 185 ms 18788 KB Output is correct
5 Correct 207 ms 18788 KB Output is correct
6 Correct 196 ms 18788 KB Output is correct
7 Correct 178 ms 18788 KB Output is correct
8 Correct 240 ms 18788 KB Output is correct
9 Correct 263 ms 18788 KB Output is correct
10 Correct 164 ms 18788 KB Output is correct
11 Correct 124 ms 18788 KB Output is correct
12 Correct 124 ms 18788 KB Output is correct
13 Correct 86 ms 18788 KB Output is correct
14 Correct 86 ms 18788 KB Output is correct
15 Correct 81 ms 18788 KB Output is correct
16 Correct 71 ms 18788 KB Output is correct
17 Correct 15 ms 18788 KB Output is correct
18 Correct 15 ms 18788 KB Output is correct
19 Correct 17 ms 18788 KB Output is correct
20 Correct 18 ms 18788 KB Output is correct
21 Correct 14 ms 18788 KB Output is correct
22 Correct 14 ms 18788 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 18788 KB Output is correct
2 Correct 223 ms 18788 KB Output is correct
3 Correct 245 ms 18788 KB Output is correct
4 Correct 174 ms 18788 KB Output is correct
5 Correct 172 ms 18788 KB Output is correct
6 Correct 161 ms 22888 KB Output is correct
7 Correct 207 ms 22888 KB Output is correct
8 Correct 236 ms 22888 KB Output is correct
9 Correct 252 ms 22888 KB Output is correct
10 Correct 204 ms 22888 KB Output is correct
11 Correct 182 ms 22888 KB Output is correct
12 Correct 175 ms 22888 KB Output is correct
13 Correct 187 ms 22888 KB Output is correct
14 Correct 136 ms 22888 KB Output is correct
15 Correct 131 ms 22888 KB Output is correct
16 Correct 82 ms 22888 KB Output is correct
17 Correct 107 ms 22888 KB Output is correct
18 Correct 141 ms 22888 KB Output is correct
19 Correct 123 ms 22888 KB Output is correct
20 Correct 93 ms 22888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 22888 KB Output is correct
2 Correct 7 ms 22888 KB Output is correct
3 Incorrect 7 ms 22888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 22888 KB Output is correct
2 Correct 141 ms 22888 KB Output is correct
3 Incorrect 182 ms 22888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4956 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 5 ms 5220 KB Output is correct
5 Correct 5 ms 5220 KB Output is correct
6 Correct 5 ms 5220 KB Output is correct
7 Incorrect 6 ms 5220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4956 KB Output is correct
2 Correct 5 ms 5220 KB Output is correct
3 Correct 5 ms 5220 KB Output is correct
4 Correct 5 ms 5220 KB Output is correct
5 Correct 5 ms 5220 KB Output is correct
6 Correct 5 ms 5220 KB Output is correct
7 Incorrect 6 ms 5220 KB Output isn't correct
8 Halted 0 ms 0 KB -