oj.uz

Submission #203547

# Submission time Handle Problem Language Result Execution time Memory
203547 2020-02-21T07:41:07 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 164 ms 54648 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() + (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;
		//cout << "now : " ;
		for (int u : c[now])
			apc += is_ap[u];//, cout << u << ' ';
		//cout << '\n';
		if (!apc){
			res += p3(c[now].size());
			return ;
		}
		//cout << "apc " << apc << '\n';
		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;
			//cout << a_with_ap - apc << ' ' << b_with_ap - 1 << ' ' << a_with_ap - apc -1 << '\n';
			res += (apc - 1) * (b_with_ap - 1) * (a_with_ap - apc) * 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);
		assert(last);
	}
}
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);
	gsz = 0, h = cnt_b;
}
void dfs(int now, int last = 0){
	static int d;
	++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);
	}
	h = 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 18 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 19 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 18 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 19 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 91 ms 34292 KB Output is correct
2 Correct 106 ms 34380 KB Output is correct
3 Correct 152 ms 40560 KB Output is correct
4 Correct 106 ms 35188 KB Output is correct
5 Correct 114 ms 35824 KB Output is correct
6 Correct 129 ms 42228 KB Output is correct
7 Correct 128 ms 35960 KB Output is correct
8 Correct 132 ms 38904 KB Output is correct
9 Correct 130 ms 33912 KB Output is correct
10 Correct 125 ms 34296 KB Output is correct
11 Correct 98 ms 29664 KB Output is correct
12 Correct 111 ms 29688 KB Output is correct
13 Correct 90 ms 29048 KB Output is correct
14 Correct 91 ms 29048 KB Output is correct
15 Correct 68 ms 27768 KB Output is correct
16 Correct 67 ms 27640 KB Output is correct
17 Correct 21 ms 22776 KB Output is correct
18 Correct 26 ms 22904 KB Output is correct
19 Correct 22 ms 22776 KB Output is correct
20 Correct 20 ms 22776 KB Output is correct
21 Correct 21 ms 22776 KB Output is correct
22 Correct 21 ms 22776 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 34292 KB Output is correct
2 Correct 135 ms 34424 KB Output is correct
3 Correct 131 ms 34424 KB Output is correct
4 Correct 128 ms 34296 KB Output is correct
5 Correct 130 ms 34296 KB Output is correct
6 Correct 164 ms 54648 KB Output is correct
7 Correct 153 ms 41848 KB Output is correct
8 Correct 150 ms 39976 KB Output is correct
9 Correct 142 ms 38140 KB Output is correct
10 Correct 134 ms 34424 KB Output is correct
11 Correct 130 ms 34296 KB Output is correct
12 Correct 127 ms 34424 KB Output is correct
13 Correct 133 ms 34296 KB Output is correct
14 Correct 130 ms 33400 KB Output is correct
15 Correct 121 ms 32760 KB Output is correct
16 Correct 76 ms 28868 KB Output is correct
17 Correct 83 ms 32880 KB Output is correct
18 Correct 78 ms 32880 KB Output is correct
19 Correct 76 ms 33004 KB Output is correct
20 Correct 91 ms 33208 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 19 ms 21624 KB Output is correct
3 Incorrect 20 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 132 ms 34296 KB Output is correct
2 Correct 132 ms 34552 KB Output is correct
3 Incorrect 140 ms 33272 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 18 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 19 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 18 ms 21496 KB Output is correct
3 Correct 19 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 19 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 -