oj.uz

Submission #51968

# Submission time Handle Problem Language Result Execution time Memory
51968 2018-06-22T18:48:15 Z pzdba Duathlon (APIO18_duathlon) C++14
66 / 100
 231 ms 51552 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

pii edges[200005];
vector<pii> g[100005];
bool idx[200005];
int low[100005], vis[100005], p[100005];
LL 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;
}

vector<int> scc[200005];
LL s[100005], sc[100005];
LL ans = 0;

void dfs2(int u, int p, int r){
	vis[u] = 1;
	s[u] += sz[u];
	sc[u] += (sz[u]-1)*(sz[u]-1);

	bool f = 0;
	for(int i=0;i<scc[u].size();i++){
		int cur = scc[u][i];

		LL s1 = 0, sc1 = 0;
		for(int j=0;j<g[cur].size();j++){
			int v = g[cur][j].first, edge = g[cur][j].second;
			int rv = root(v);
			if(!idx[edge]) continue;
			if(rv == p) continue;
			dfs2(rv, u, v);

			ans += sc[rv]*s[u]; // sc - f
			ans += s[rv]*sc[u]; // s - cf 

			ans += s[rv]*s1; // s - c - f

			s1 += s[rv];
			s[u] += s[rv];
			sc[u] += sc[rv];
		}

		for(int j=0;j<g[cur].size();j++){
			int v = g[cur][j].first, edge = g[cur][j].second;
			int rv = root(v);
			if(!idx[edge]) continue;
			if(rv == p) continue;

			if(cur == r) f = 1;

			sc[u] += s[rv]*sz[u];
		}
	}

	if(f){
		int cur = r;
		for(int j=0;j<g[cur].size();j++){
			int v = g[cur][j].first, edge = g[cur][j].second;
			int rv = root(v);
			if(!idx[edge]) continue;
			if(rv == p) continue;

			sc[u] -= s[rv]*sz[u];
			sc[u] += s[rv];
		}
	}
}

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));
		edges[i] = pii(a, b);
	}
	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);
			}
		}
	}
	for(int i=1;i<=n;i++){
		scc[root(i)].push_back(i);
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
	 	if(root(i) == i) dfs2(i, 0, 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:13: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 'void dfs2(int, int, int)':
count_triplets.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<scc[u].size();i++){
              ~^~~~~~~~~~~~~~
count_triplets.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[cur].size();j++){
               ~^~~~~~~~~~~~~~
count_triplets.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[cur].size();j++){
               ~^~~~~~~~~~~~~~
count_triplets.cpp:53:14: warning: unused variable 'sc1' [-Wunused-variable]
   LL s1 = 0, sc1 = 0;
              ^~~
count_triplets.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[cur].size();j++){
               ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++){
               ~^~~~~~~~~~~~
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", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7800 KB Output is correct
2 Correct 7 ms 7860 KB Output is correct
3 Correct 8 ms 7984 KB Output is correct
4 Correct 10 ms 7984 KB Output is correct
5 Correct 8 ms 7984 KB Output is correct
6 Correct 8 ms 7996 KB Output is correct
7 Correct 9 ms 7996 KB Output is correct
8 Incorrect 8 ms 8076 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 95 ms 21936 KB Output is correct
2 Correct 100 ms 21960 KB Output is correct
3 Correct 130 ms 21960 KB Output is correct
4 Correct 132 ms 22144 KB Output is correct
5 Correct 138 ms 22144 KB Output is correct
6 Correct 123 ms 22144 KB Output is correct
7 Correct 182 ms 22144 KB Output is correct
8 Correct 167 ms 22144 KB Output is correct
9 Correct 127 ms 22144 KB Output is correct
10 Correct 187 ms 22144 KB Output is correct
11 Correct 127 ms 22144 KB Output is correct
12 Correct 151 ms 22144 KB Output is correct
13 Correct 118 ms 22144 KB Output is correct
14 Correct 104 ms 22144 KB Output is correct
15 Correct 93 ms 22144 KB Output is correct
16 Correct 109 ms 22144 KB Output is correct
17 Correct 20 ms 22144 KB Output is correct
18 Correct 20 ms 22144 KB Output is correct
19 Correct 21 ms 22144 KB Output is correct
20 Correct 23 ms 22144 KB Output is correct
21 Correct 22 ms 22144 KB Output is correct
22 Correct 20 ms 22144 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 22144 KB Output is correct
2 Correct 140 ms 22144 KB Output is correct
3 Correct 146 ms 22144 KB Output is correct
4 Correct 135 ms 22144 KB Output is correct
5 Correct 130 ms 22144 KB Output is correct
6 Correct 165 ms 23436 KB Output is correct
7 Correct 170 ms 23436 KB Output is correct
8 Correct 173 ms 23436 KB Output is correct
9 Correct 144 ms 23436 KB Output is correct
10 Correct 158 ms 23436 KB Output is correct
11 Correct 133 ms 23436 KB Output is correct
12 Correct 130 ms 23436 KB Output is correct
13 Correct 125 ms 23436 KB Output is correct
14 Correct 131 ms 23436 KB Output is correct
15 Correct 110 ms 23436 KB Output is correct
16 Correct 75 ms 23436 KB Output is correct
17 Correct 92 ms 23436 KB Output is correct
18 Correct 91 ms 23436 KB Output is correct
19 Correct 102 ms 23436 KB Output is correct
20 Correct 92 ms 23436 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 23436 KB Output is correct
2 Correct 142 ms 23436 KB Output is correct
3 Correct 165 ms 23436 KB Output is correct
4 Correct 154 ms 23436 KB Output is correct
5 Correct 144 ms 23436 KB Output is correct
6 Correct 133 ms 23436 KB Output is correct
7 Correct 144 ms 23436 KB Output is correct
8 Correct 172 ms 23620 KB Output is correct
9 Correct 112 ms 24776 KB Output is correct
10 Correct 115 ms 25920 KB Output is correct
11 Correct 113 ms 26916 KB Output is correct
12 Correct 95 ms 27612 KB Output is correct
13 Correct 104 ms 28756 KB Output is correct
14 Correct 105 ms 31380 KB Output is correct
15 Correct 169 ms 37676 KB Output is correct
16 Correct 231 ms 38768 KB Output is correct
17 Correct 191 ms 40844 KB Output is correct
18 Correct 177 ms 40844 KB Output is correct
19 Correct 207 ms 40844 KB Output is correct
20 Correct 169 ms 41496 KB Output is correct
21 Correct 162 ms 42780 KB Output is correct
22 Correct 157 ms 43884 KB Output is correct
23 Correct 138 ms 44760 KB Output is correct
24 Correct 152 ms 47600 KB Output is correct
25 Correct 229 ms 49200 KB Output is correct
26 Correct 155 ms 50216 KB Output is correct
27 Correct 160 ms 51552 KB Output is correct

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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