oj.uz

Submission #203528

# Submission time Handle Problem Language Result Execution time Memory
203528 2020-02-21T06:36:10 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
8 / 100
 141 ms 42100 KB 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 300010;
int n, m;
vector<int> edge[maxn];
int low[maxn], st[maxn], stl, dep[maxn];
int cnt_b;
ll gsz;
vector<int> c[maxn];
bool is_ap[maxn];
ll res;
int h;
#define c2(i) ((ll)(i) * ((ll)(i)-1) / 2)
#define p3(i) ((ll)(i) * ((ll)(i)-1) * ((ll)(i)-2))
vector<int> tree_edge[maxn];
int sz[maxn];
void dfs2(int now, int last = 0){
	sz[now] = c[now].size();
	for (int u : tree_edge[now]) if(u != last) {
		dfs2(u, now);
		sz[now] += sz[u] - (now > n);
		assert((sz[u] - (now)>n) >= 0);
	}
	if (now > n){
		ll apc = 0;
		for (int u : c[now])
			apc += is_ap[u];
		auto add = [&](ll a_with_ap, ll b_with_ap, ll all) {
			res += (a_with_ap - apc) * (b_with_ap) * (a_with_ap - apc - 1) * 2;
			res += (b_with_ap) * (all - a_with_ap - b_with_ap + 1) * (a_with_ap - apc);
		};
		for (int u : tree_edge[now]) if(u != last) {
			add(c[now].size(), sz[u], gsz);
		}
		if (last)
			add(c[now].size(), gsz - sz[now]+1, gsz);
		res += p3(c[now].size());
	}
	else {
		auto add = [&](ll a, ll all){
			res += (a-1) * (all-a);
		};
		for (int u : tree_edge[now]) if(u != last)
			add(sz[u], gsz);
		if (last)
			add(gsz - sz[now]+1, gsz);
	}
}
void cal(){
	for (int i = h;i < cnt_b;++i){
		for (int u : c[i]) if (is_ap[u]) {
			tree_edge[u].pb(i);
			tree_edge[i].pb(u);
		}
	}
	dfs2(h);
}


void dfs(int now, int last = 0){
	static int d;
	if (last == 0) {
		gsz = 0;
		h = cnt_b;
	}
	++gsz;
	low[now] = dep[now] = ++d;
	st[stl++] = now;
	int cnt_c = 0;
	for (int u : edge[now]) if (u != last) {
		if (!low[u]){
			dfs(u, now);
			++cnt_c;
			low[now] = min(low[now], low[u]);
			if (low[u] >= dep[now]){
				do {
					c[cnt_b].pb( st[--stl] );
				} while (st[stl] != u);
				c[cnt_b++].pb(now);
				is_ap[now] = true;
			}
		}
		else 
			low[now] = min(low[now], dep[u]);
	}
	if (last == 0 && cnt_c < 2)
		is_ap[now] = false;
	--d;
	if (last == 0)
		cal();
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for ( int a, b, i = 0 ; i < m ; ++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	cnt_b = n+1;
	for (int i = 1;i <= n;++i) if (!low[i])
		dfs(i);
	cout << res << '\n';
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from count_triplets.cpp:1:
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:24:28: warning: comparison of constant '0' with boolean expression is always true [-Wbool-compare]
   assert((sz[u] - (now)>n) >= 0);
          ~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21496 KB Output is correct
2 Correct 16 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 17 ms 21496 KB Output is correct
7 Incorrect 17 ms 21496 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 94 ms 34292 KB Output is correct
2 Correct 101 ms 34292 KB Output is correct
3 Correct 128 ms 40600 KB Output is correct
4 Correct 108 ms 35188 KB Output is correct
5 Correct 124 ms 35828 KB Output is correct
6 Correct 125 ms 42100 KB Output is correct
7 Correct 138 ms 35960 KB Output is correct
8 Correct 141 ms 38904 KB Output is correct
9 Correct 128 ms 33912 KB Output is correct
10 Correct 124 ms 34296 KB Output is correct
11 Correct 99 ms 29624 KB Output is correct
12 Correct 98 ms 29560 KB Output is correct
13 Correct 88 ms 29048 KB Output is correct
14 Correct 89 ms 29048 KB Output is correct
15 Correct 69 ms 27768 KB Output is correct
16 Correct 70 ms 27640 KB Output is correct
17 Correct 20 ms 22776 KB Output is correct
18 Correct 20 ms 22776 KB Output is correct
19 Correct 20 ms 22776 KB Output is correct
20 Correct 20 ms 22776 KB Output is correct
21 Correct 19 ms 22776 KB Output is correct
22 Correct 19 ms 22776 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 21624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 34296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 21624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 34296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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