oj.uz

Submission #203538

# Submission time Handle Problem Language Result Execution time Memory
203538 2020-02-21T06:59:36 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 160 ms 54652 KB 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#define int ll
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() + (now <= n);
	for (int u : tree_edge[now]) if(u != last) {
		dfs2(u, now);
		sz[now] += sz[u] - 1;
	}
	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 - 1) * (a_with_ap - apc - 1) * 2;
			//res += (b_with_ap - 1) * (all - a_with_ap - b_with_ap + 1) * (a_with_ap - apc);
			res += (a_with_ap - apc) * (b_with_ap - 1) * (a_with_ap - apc - 1) * 2;
			res += (b_with_ap - 1) * (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';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21496 KB Output is correct
2 Correct 20 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 19 ms 21496 KB Output is correct
5 Correct 18 ms 21496 KB Output is correct
6 Correct 19 ms 21496 KB Output is correct
7 Incorrect 18 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 18 ms 21496 KB Output is correct
2 Correct 20 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 19 ms 21496 KB Output is correct
5 Correct 18 ms 21496 KB Output is correct
6 Correct 19 ms 21496 KB Output is correct
7 Incorrect 18 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 96 ms 35696 KB Output is correct
2 Correct 108 ms 35656 KB Output is correct
3 Correct 124 ms 42072 KB Output is correct
4 Correct 111 ms 37356 KB Output is correct
5 Correct 118 ms 37744 KB Output is correct
6 Correct 137 ms 43504 KB Output is correct
7 Correct 133 ms 38296 KB Output is correct
8 Correct 128 ms 40824 KB Output is correct
9 Correct 135 ms 36472 KB Output is correct
10 Correct 127 ms 36596 KB Output is correct
11 Correct 106 ms 32468 KB Output is correct
12 Correct 104 ms 32376 KB Output is correct
13 Correct 94 ms 31736 KB Output is correct
14 Correct 93 ms 31608 KB Output is correct
15 Correct 72 ms 30048 KB Output is correct
16 Correct 83 ms 30072 KB Output is correct
17 Correct 22 ms 24056 KB Output is correct
18 Correct 22 ms 23928 KB Output is correct
19 Correct 23 ms 23928 KB Output is correct
20 Correct 23 ms 23928 KB Output is correct
21 Correct 22 ms 23928 KB Output is correct
22 Correct 21 ms 23928 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 38240 KB Output is correct
2 Correct 144 ms 38136 KB Output is correct
3 Correct 137 ms 38136 KB Output is correct
4 Correct 143 ms 38312 KB Output is correct
5 Correct 134 ms 38136 KB Output is correct
6 Correct 160 ms 54652 KB Output is correct
7 Correct 160 ms 44536 KB Output is correct
8 Correct 151 ms 42872 KB Output is correct
9 Correct 147 ms 41336 KB Output is correct
10 Correct 146 ms 38136 KB Output is correct
11 Correct 137 ms 38264 KB Output is correct
12 Correct 135 ms 38136 KB Output is correct
13 Correct 144 ms 38136 KB Output is correct
14 Correct 140 ms 36984 KB Output is correct
15 Correct 116 ms 35576 KB Output is correct
16 Correct 77 ms 31224 KB Output is correct
17 Correct 84 ms 36076 KB Output is correct
18 Correct 85 ms 36072 KB Output is correct
19 Correct 87 ms 36504 KB Output is correct
20 Correct 86 ms 36200 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21624 KB Output is correct
2 Correct 20 ms 21628 KB Output is correct
3 Incorrect 19 ms 21624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 38124 KB Output is correct
2 Correct 153 ms 38392 KB Output is correct
3 Incorrect 149 ms 37496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21496 KB Output is correct
2 Correct 20 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 19 ms 21496 KB Output is correct
5 Correct 18 ms 21496 KB Output is correct
6 Correct 19 ms 21496 KB Output is correct
7 Incorrect 18 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 18 ms 21496 KB Output is correct
2 Correct 20 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 19 ms 21496 KB Output is correct
5 Correct 18 ms 21496 KB Output is correct
6 Correct 19 ms 21496 KB Output is correct
7 Incorrect 18 ms 21496 KB Output isn't correct
8 Halted 0 ms 0 KB -