oj.uz

Submission #203556

# Submission time Handle Problem Language Result Execution time Memory
203556 2020-02-21T08:24:46 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 165 ms 54776 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 ;
		}
//		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);
//		};
//
		ll o = res;
		auto add = [&](ll a_with_ap, ll b_with_ap, ll all) {
			res += (b_with_ap) * (all - a_with_ap - b_with_ap + 1) * (a_with_ap - apc);
			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';
	}
	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';
}

Compilation message

count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:41:6: warning: unused variable 'o' [-Wunused-variable]
   ll o = res;
      ^

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 21624 KB Output is correct
4 Correct 20 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 23 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 21624 KB Output is correct
4 Correct 20 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 23 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 89 ms 34296 KB Output is correct
2 Correct 104 ms 34340 KB Output is correct
3 Correct 126 ms 40564 KB Output is correct
4 Correct 102 ms 35188 KB Output is correct
5 Correct 113 ms 35828 KB Output is correct
6 Correct 130 ms 42072 KB Output is correct
7 Correct 135 ms 35960 KB Output is correct
8 Correct 136 ms 38908 KB Output is correct
9 Correct 133 ms 33916 KB Output is correct
10 Correct 123 ms 34304 KB Output is correct
11 Correct 101 ms 29688 KB Output is correct
12 Correct 103 ms 29560 KB Output is correct
13 Correct 92 ms 29308 KB Output is correct
14 Correct 88 ms 29048 KB Output is correct
15 Correct 71 ms 27768 KB Output is correct
16 Correct 70 ms 27640 KB Output is correct
17 Correct 22 ms 22776 KB Output is correct
18 Correct 21 ms 22776 KB Output is correct
19 Correct 21 ms 22776 KB Output is correct
20 Correct 21 ms 22776 KB Output is correct
21 Correct 20 ms 22780 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 18 ms 21624 KB Output is correct
2 Correct 19 ms 21624 KB Output is correct
3 Correct 19 ms 21624 KB Output is correct
4 Correct 20 ms 21752 KB Output is correct
5 Correct 19 ms 21752 KB Output is correct
6 Correct 20 ms 21752 KB Output is correct
7 Correct 19 ms 21752 KB Output is correct
8 Correct 19 ms 21752 KB Output is correct
9 Correct 19 ms 21624 KB Output is correct
10 Correct 19 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 19 ms 21624 KB Output is correct
14 Correct 20 ms 21624 KB Output is correct
15 Correct 19 ms 21624 KB Output is correct
16 Correct 19 ms 21624 KB Output is correct
17 Correct 19 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 130 ms 34296 KB Output is correct
2 Correct 136 ms 34472 KB Output is correct
3 Correct 131 ms 34296 KB Output is correct
4 Correct 132 ms 34296 KB Output is correct
5 Correct 128 ms 34296 KB Output is correct
6 Correct 165 ms 54776 KB Output is correct
7 Correct 144 ms 41848 KB Output is correct
8 Correct 140 ms 40056 KB Output is correct
9 Correct 144 ms 38116 KB Output is correct
10 Correct 134 ms 34424 KB Output is correct
11 Correct 125 ms 34424 KB Output is correct
12 Correct 128 ms 34424 KB Output is correct
13 Correct 129 ms 34352 KB Output is correct
14 Correct 135 ms 33656 KB Output is correct
15 Correct 115 ms 32504 KB Output is correct
16 Correct 73 ms 28920 KB Output is correct
17 Correct 78 ms 32880 KB Output is correct
18 Correct 79 ms 32880 KB Output is correct
19 Correct 85 ms 33004 KB Output is correct
20 Correct 79 ms 32888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21624 KB Output is correct
2 Correct 19 ms 21624 KB Output is correct
3 Incorrect 24 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 134 ms 34352 KB Output is correct
2 Correct 132 ms 34552 KB Output is correct
3 Incorrect 135 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 21624 KB Output is correct
4 Correct 20 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 23 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 21624 KB Output is correct
4 Correct 20 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 23 ms 21496 KB Output isn't correct
8 Halted 0 ms 0 KB -