oj.uz

Submission #51917

# Submission time Handle Problem Language Result Execution time Memory
51917 2018-06-22T16:19:28 Z pzdba Duathlon (APIO18_duathlon) C++14
31 / 100
 265 ms 50200 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

vector<pii> g[100005];
set<int> gs[100005];
bool idx[200005];
int low[100005], vis[100005], p[100005], sz[100005], T = 1;
void dfs1(int u, int p){
	vis[u] = low[u] = T++;
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i].first;
		if(v == p) continue;
		if(vis[v]) low[u] = min(low[u], vis[v]);
		else{
			dfs1(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > vis[u]) idx[g[u][i].second] = 1;
		}
	}
}

int root(int a){
	while(p[a] != a){
		p[a] = p[p[a]];
		a = p[a];
	}
	return a;
}
bool merge(int a, int b){
	a = root(a), b = root(b);
	if(a == b) return 0;
	sz[b] += sz[a];
	p[a] = b;
	return 1;
}

LL s[100005], sc[100005];
LL ans = 0;

void dfs2(int u, int p){
	vis[u] = 1;
	for(set<int>::iterator its=gs[u].begin();its != gs[u].end();its++){
		int v = *its;
		if(v == p) continue;
		dfs2(v, u);

		ans += (LL)sc[v]*sz[u]; // f
		if(sz[u] > 1) ans += (LL)s[v]*(sz[u]-1 + (LL)(sz[u]-1)*(sz[u]-2)); // cf

		ans += (LL)sc[v]*s[u]; // f
		ans += (LL)s[v]*sc[u]; // cf

		s[u] += s[v];
		sc[u] += sc[v];
		sc[u] += (LL)s[v]*sz[u];
	}
	s[u] += sz[u];
	sc[u] += (LL)(sz[u]-1)*(sz[u]-1);
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(pii(b, i));
		g[b].push_back(pii(a, i));
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs1(i, 0);
	}
	for(int i=1;i<=n;i++) p[i] = i, sz[i] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int v = g[i][j].first, edge = g[i][j].second;
			if(!idx[edge]){
				merge(i, v);
			}
		}
	}
	int r = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<g[i].size();j++){
			int v = g[i][j].first, edge = g[i][j].second;
			if(!idx[edge]) continue;
			if(root(i) == root(v)) continue; 
			gs[root(i)].insert(root(v));
			gs[root(v)].insert(root(i));
		}
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
	 	if(root(i) == i) dfs2(i, 0);
	}
	ans *= 2;
	for(int i=1;i<=n;i++){
		if(root(i) == i){
			ans += (LL)sz[i]*(sz[i]-1)*(sz[i]-2);
		}
	}
	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
               ~^~~~~~~~~~~~
count_triplets.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
               ~^~~~~~~~~~~~
count_triplets.cpp:85:6: warning: unused variable 'r' [-Wunused-variable]
  int r = 0;
      ^
count_triplets.cpp:65: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:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 10 ms 7888 KB Output is correct
3 Correct 9 ms 7888 KB Output is correct
4 Correct 8 ms 7892 KB Output is correct
5 Correct 9 ms 7892 KB Output is correct
6 Correct 8 ms 7936 KB Output is correct
7 Incorrect 8 ms 7996 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 10 ms 7888 KB Output is correct
3 Correct 9 ms 7888 KB Output is correct
4 Correct 8 ms 7892 KB Output is correct
5 Correct 9 ms 7892 KB Output is correct
6 Correct 8 ms 7936 KB Output is correct
7 Incorrect 8 ms 7996 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 162 ms 20156 KB Output is correct
2 Correct 110 ms 20156 KB Output is correct
3 Correct 251 ms 22484 KB Output is correct
4 Correct 148 ms 23380 KB Output is correct
5 Correct 191 ms 23380 KB Output is correct
6 Correct 235 ms 25660 KB Output is correct
7 Correct 205 ms 26204 KB Output is correct
8 Correct 193 ms 28124 KB Output is correct
9 Correct 201 ms 28124 KB Output is correct
10 Correct 182 ms 28884 KB Output is correct
11 Correct 124 ms 28884 KB Output is correct
12 Correct 168 ms 28884 KB Output is correct
13 Correct 130 ms 29232 KB Output is correct
14 Correct 128 ms 29924 KB Output is correct
15 Correct 96 ms 29964 KB Output is correct
16 Correct 97 ms 30492 KB Output is correct
17 Correct 14 ms 30492 KB Output is correct
18 Correct 13 ms 30492 KB Output is correct
19 Correct 13 ms 30492 KB Output is correct
20 Correct 13 ms 30492 KB Output is correct
21 Correct 13 ms 30492 KB Output is correct
22 Correct 14 ms 30492 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 38304 KB Output is correct
2 Correct 204 ms 38420 KB Output is correct
3 Correct 207 ms 38420 KB Output is correct
4 Correct 195 ms 38420 KB Output is correct
5 Correct 196 ms 38420 KB Output is correct
6 Correct 239 ms 42116 KB Output is correct
7 Correct 222 ms 42116 KB Output is correct
8 Correct 262 ms 42116 KB Output is correct
9 Correct 226 ms 42116 KB Output is correct
10 Correct 206 ms 42116 KB Output is correct
11 Correct 249 ms 42116 KB Output is correct
12 Correct 192 ms 42116 KB Output is correct
13 Correct 203 ms 42116 KB Output is correct
14 Correct 173 ms 42116 KB Output is correct
15 Correct 163 ms 42116 KB Output is correct
16 Correct 96 ms 42116 KB Output is correct
17 Correct 265 ms 46308 KB Output is correct
18 Correct 193 ms 47580 KB Output is correct
19 Correct 189 ms 48844 KB Output is correct
20 Correct 216 ms 50200 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 50200 KB Output is correct
2 Correct 11 ms 50200 KB Output is correct
3 Incorrect 10 ms 50200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 50200 KB Output is correct
2 Correct 261 ms 50200 KB Output is correct
3 Incorrect 213 ms 50200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 10 ms 7888 KB Output is correct
3 Correct 9 ms 7888 KB Output is correct
4 Correct 8 ms 7892 KB Output is correct
5 Correct 9 ms 7892 KB Output is correct
6 Correct 8 ms 7936 KB Output is correct
7 Incorrect 8 ms 7996 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 10 ms 7888 KB Output is correct
3 Correct 9 ms 7888 KB Output is correct
4 Correct 8 ms 7892 KB Output is correct
5 Correct 9 ms 7892 KB Output is correct
6 Correct 8 ms 7936 KB Output is correct
7 Incorrect 8 ms 7996 KB Output isn't correct
8 Halted 0 ms 0 KB -