oj.uz

Submission #203534

# Submission time Handle Problem Language Result Execution time Memory
203534 2020-02-21T06:50:23 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 174 ms 55928 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;
		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 21 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 21 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 20 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 18 ms 21496 KB Output is correct
2 Correct 21 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 21 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 20 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 101 ms 34268 KB Output is correct
2 Correct 118 ms 34268 KB Output is correct
3 Correct 145 ms 40540 KB Output is correct
4 Correct 114 ms 35188 KB Output is correct
5 Correct 123 ms 35804 KB Output is correct
6 Correct 153 ms 42076 KB Output is correct
7 Correct 153 ms 35960 KB Output is correct
8 Correct 148 ms 38956 KB Output is correct
9 Correct 139 ms 33904 KB Output is correct
10 Correct 145 ms 34296 KB Output is correct
11 Correct 108 ms 29688 KB Output is correct
12 Correct 114 ms 29560 KB Output is correct
13 Correct 86 ms 29080 KB Output is correct
14 Correct 91 ms 29048 KB Output is correct
15 Correct 68 ms 27768 KB Output is correct
16 Correct 84 ms 27640 KB Output is correct
17 Correct 22 ms 22808 KB Output is correct
18 Correct 29 ms 22780 KB Output is correct
19 Correct 28 ms 22776 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 21 ms 21752 KB Output is correct
2 Correct 19 ms 21676 KB Output is correct
3 Correct 18 ms 21624 KB Output is correct
4 Correct 18 ms 21880 KB Output is correct
5 Correct 17 ms 21752 KB Output is correct
6 Correct 17 ms 21752 KB Output is correct
7 Correct 19 ms 21880 KB Output is correct
8 Correct 17 ms 21624 KB Output is correct
9 Correct 17 ms 21624 KB Output is correct
10 Correct 20 ms 21624 KB Output is correct
11 Correct 20 ms 21624 KB Output is correct
12 Correct 19 ms 21624 KB Output is correct
13 Correct 17 ms 21624 KB Output is correct
14 Correct 23 ms 21624 KB Output is correct
15 Correct 17 ms 21624 KB Output is correct
16 Correct 17 ms 21624 KB Output is correct
17 Correct 17 ms 21624 KB Output is correct
18 Correct 18 ms 21624 KB Output is correct
19 Correct 18 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 150 ms 35020 KB Output is correct
2 Correct 140 ms 35576 KB Output is correct
3 Correct 148 ms 35564 KB Output is correct
4 Correct 148 ms 35576 KB Output is correct
5 Correct 132 ms 35576 KB Output is correct
6 Correct 169 ms 55928 KB Output is correct
7 Correct 174 ms 43128 KB Output is correct
8 Correct 158 ms 41208 KB Output is correct
9 Correct 147 ms 39416 KB Output is correct
10 Correct 159 ms 35568 KB Output is correct
11 Correct 147 ms 35616 KB Output is correct
12 Correct 141 ms 35576 KB Output is correct
13 Correct 144 ms 35704 KB Output is correct
14 Correct 129 ms 34552 KB Output is correct
15 Correct 117 ms 33444 KB Output is correct
16 Correct 81 ms 29560 KB Output is correct
17 Correct 100 ms 34196 KB Output is correct
18 Correct 91 ms 34160 KB Output is correct
19 Correct 85 ms 34284 KB Output is correct
20 Correct 89 ms 34168 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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