oj.uz

Submission #203563

# Submission time Handle Problem Language Result Execution time Memory
203563 2020-02-21T09:35:33 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 176 ms 54716 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;
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;
	}
	ll o = res;
	if (now > n){
		ll apc = 0, cur = c[now].size();
		//cout << "now ";
		for (int u : c[now]) {
			apc += is_ap[u];
			//cout << u << ' ';
		}
		//cout << '\n';
		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 + apc) * (cur-2);
		if (last)
			res += (gsz - sz[now]+1) * (sz[now] - cur +apc-1) * (cur-2);
	}
	else {
		//cout << "now " << now << '\n';
		auto add = [&](ll a, ll all){
			//cout << "ad " << a << '\n';
			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);
	}
//	cout << "dif + " << res-o << '\n';
//	cout << '\n';
}
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 && 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:23:5: warning: unused variable 'o' [-Wunused-variable]
  ll o = res;
     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21500 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 18 ms 21496 KB Output is correct
7 Correct 17 ms 21496 KB Output is correct
8 Correct 17 ms 21496 KB Output is correct
9 Correct 18 ms 21496 KB Output is correct
10 Correct 18 ms 21496 KB Output is correct
11 Incorrect 18 ms 21496 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21500 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 18 ms 21496 KB Output is correct
7 Correct 17 ms 21496 KB Output is correct
8 Correct 17 ms 21496 KB Output is correct
9 Correct 18 ms 21496 KB Output is correct
10 Correct 18 ms 21496 KB Output is correct
11 Incorrect 18 ms 21496 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 34292 KB Output is correct
2 Correct 99 ms 34444 KB Output is correct
3 Correct 121 ms 40564 KB Output is correct
4 Correct 116 ms 35188 KB Output is correct
5 Correct 107 ms 35828 KB Output is correct
6 Correct 134 ms 42100 KB Output is correct
7 Correct 131 ms 35960 KB Output is correct
8 Correct 139 ms 39160 KB Output is correct
9 Correct 131 ms 33912 KB Output is correct
10 Correct 124 ms 34296 KB Output is correct
11 Correct 98 ms 29688 KB Output is correct
12 Correct 98 ms 29564 KB Output is correct
13 Correct 88 ms 29176 KB Output is correct
14 Correct 87 ms 29048 KB Output is correct
15 Correct 67 ms 27768 KB Output is correct
16 Correct 68 ms 27768 KB Output is correct
17 Correct 21 ms 22776 KB Output is correct
18 Correct 21 ms 22776 KB Output is correct
19 Correct 20 ms 22780 KB Output is correct
20 Correct 20 ms 22780 KB Output is correct
21 Correct 20 ms 22776 KB Output is correct
22 Correct 22 ms 22720 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 18 ms 21624 KB Output is correct
3 Correct 22 ms 21752 KB Output is correct
4 Correct 21 ms 21880 KB Output is correct
5 Correct 19 ms 21752 KB Output is correct
6 Correct 18 ms 21752 KB Output is correct
7 Correct 19 ms 21880 KB Output is correct
8 Correct 18 ms 21624 KB Output is correct
9 Correct 20 ms 21624 KB Output is correct
10 Correct 18 ms 21624 KB Output is correct
11 Correct 19 ms 21624 KB Output is correct
12 Correct 18 ms 21628 KB Output is correct
13 Correct 18 ms 21624 KB Output is correct
14 Correct 19 ms 21624 KB Output is correct
15 Correct 18 ms 21624 KB Output is correct
16 Correct 18 ms 21496 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 21752 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 34292 KB Output is correct
2 Correct 133 ms 34296 KB Output is correct
3 Correct 129 ms 34300 KB Output is correct
4 Correct 132 ms 34424 KB Output is correct
5 Correct 129 ms 34296 KB Output is correct
6 Correct 176 ms 54716 KB Output is correct
7 Correct 147 ms 41848 KB Output is correct
8 Correct 147 ms 40056 KB Output is correct
9 Correct 147 ms 38136 KB Output is correct
10 Correct 129 ms 34292 KB Output is correct
11 Correct 132 ms 34424 KB Output is correct
12 Correct 136 ms 34552 KB Output is correct
13 Correct 130 ms 34296 KB Output is correct
14 Correct 124 ms 33400 KB Output is correct
15 Correct 116 ms 32376 KB Output is correct
16 Correct 72 ms 28944 KB Output is correct
17 Correct 77 ms 32880 KB Output is correct
18 Correct 77 ms 32880 KB Output is correct
19 Correct 77 ms 33004 KB Output is correct
20 Correct 80 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 21676 KB Output is correct
3 Incorrect 18 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 131 ms 34296 KB Output is correct
2 Correct 136 ms 34548 KB Output is correct
3 Incorrect 136 ms 33260 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 21500 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 18 ms 21496 KB Output is correct
7 Correct 17 ms 21496 KB Output is correct
8 Correct 17 ms 21496 KB Output is correct
9 Correct 18 ms 21496 KB Output is correct
10 Correct 18 ms 21496 KB Output is correct
11 Incorrect 18 ms 21496 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21500 KB Output is correct
2 Correct 18 ms 21496 KB Output is correct
3 Correct 18 ms 21496 KB Output is correct
4 Correct 18 ms 21496 KB Output is correct
5 Correct 17 ms 21496 KB Output is correct
6 Correct 18 ms 21496 KB Output is correct
7 Correct 17 ms 21496 KB Output is correct
8 Correct 17 ms 21496 KB Output is correct
9 Correct 18 ms 21496 KB Output is correct
10 Correct 18 ms 21496 KB Output is correct
11 Incorrect 18 ms 21496 KB Output isn't correct
12 Halted 0 ms 0 KB -