oj.uz

Submission #203558

# Submission time Handle Problem Language Result Execution time Memory
203558 2020-02-21T08:47:35 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 154 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 << ' ';
//		if (!apc){
//			res += p3(c[now].size());
//			return ;
//		}
//		ll o = res;
//		auto add = [&](ll a_with_ap, ll b_with_ap, ll all) {
//			res += 2 * (b_with_ap) * (a_with_ap - 1 - apc) * (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 += ((ll)c[now].size()-apc) * ((ll)c[now].size()-apc-1) * ((ll)c[now].size()-2);
//		//cout << " add " << res-o << '\n';
//	}
	if (now > n){
		ll apc = 0, cur = c[now].size();
		//cout << "now ";
		for (int u : c[now])
			apc += is_ap[u];//, cout << u << ' ';
		res += (cur-apc) * (gsz - cur + apc) * (cur-apc-1) * 2;
		res += (cur-apc) * (cur-apc-1) * (cur-2);
		for (int u : tree_edge[now]) if(u != last)
			res += sz[u] * (gsz - sz[u] - cur + 1) * (cur-apc);
		if (last)
			res += (gsz - sz[now]+1) * (sz[now] - c[now].size()+apc-1) * (cur-apc);
	}
	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 19 ms 21496 KB Output is correct
2 Correct 19 ms 21496 KB Output is correct
3 Correct 18 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 18 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 19 ms 21496 KB Output is correct
2 Correct 19 ms 21496 KB Output is correct
3 Correct 18 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 18 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 34292 KB Output is correct
2 Correct 102 ms 34344 KB Output is correct
3 Correct 119 ms 40564 KB Output is correct
4 Correct 103 ms 35172 KB Output is correct
5 Correct 108 ms 35828 KB Output is correct
6 Correct 129 ms 42100 KB Output is correct
7 Correct 135 ms 36088 KB Output is correct
8 Correct 131 ms 38904 KB Output is correct
9 Correct 136 ms 33912 KB Output is correct
10 Correct 119 ms 34296 KB Output is correct
11 Correct 110 ms 29820 KB Output is correct
12 Correct 100 ms 29688 KB Output is correct
13 Correct 89 ms 29044 KB Output is correct
14 Correct 89 ms 29048 KB Output is correct
15 Correct 68 ms 27768 KB Output is correct
16 Correct 76 ms 27828 KB Output is correct
17 Correct 21 ms 22776 KB Output is correct
18 Correct 22 ms 22776 KB Output is correct
19 Correct 21 ms 22824 KB Output is correct
20 Correct 21 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 19 ms 21592 KB Output is correct
2 Correct 21 ms 21624 KB Output is correct
3 Correct 20 ms 21624 KB Output is correct
4 Correct 20 ms 21752 KB Output is correct
5 Correct 20 ms 21752 KB Output is correct
6 Correct 19 ms 21752 KB Output is correct
7 Correct 20 ms 21752 KB Output is correct
8 Correct 20 ms 21624 KB Output is correct
9 Correct 19 ms 21756 KB Output is correct
10 Correct 19 ms 21628 KB Output is correct
11 Correct 20 ms 21624 KB Output is correct
12 Correct 20 ms 21624 KB Output is correct
13 Correct 19 ms 21756 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 21496 KB Output is correct
17 Correct 18 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 19 ms 21624 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 34424 KB Output is correct
2 Correct 135 ms 34296 KB Output is correct
3 Correct 133 ms 34424 KB Output is correct
4 Correct 127 ms 34296 KB Output is correct
5 Correct 123 ms 34424 KB Output is correct
6 Correct 154 ms 54648 KB Output is correct
7 Correct 145 ms 41848 KB Output is correct
8 Correct 139 ms 39928 KB Output is correct
9 Correct 139 ms 38136 KB Output is correct
10 Correct 134 ms 34296 KB Output is correct
11 Correct 127 ms 34424 KB Output is correct
12 Correct 135 ms 34296 KB Output is correct
13 Correct 131 ms 34296 KB Output is correct
14 Correct 130 ms 33528 KB Output is correct
15 Correct 114 ms 32504 KB Output is correct
16 Correct 74 ms 28920 KB Output is correct
17 Correct 81 ms 32860 KB Output is correct
18 Correct 77 ms 32880 KB Output is correct
19 Correct 83 ms 33004 KB Output is correct
20 Correct 81 ms 32888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21624 KB Output is correct
2 Correct 21 ms 21624 KB Output is correct
3 Incorrect 22 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 128 ms 34296 KB Output is correct
2 Correct 135 ms 34684 KB Output is correct
3 Incorrect 141 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 19 ms 21496 KB Output is correct
2 Correct 19 ms 21496 KB Output is correct
3 Correct 18 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 18 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 19 ms 21496 KB Output is correct
2 Correct 19 ms 21496 KB Output is correct
3 Correct 18 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 18 ms 21496 KB Output is correct
7 Incorrect 18 ms 21496 KB Output isn't correct
8 Halted 0 ms 0 KB -