oj.uz

Submission #203526

# Submission time Handle Problem Language Result Execution time Memory
203526 2020-02-21T06:27:40 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
8 / 100
 158 ms 57460 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<<1];
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<<1];
int sz[maxn<<1];
void dfs2(int now, int last = 0){
	sz[now] = c[now].size();
	for (int u : tree_edge[now]) if(u != last) {
		dfs2(u, now);
		sz[now] += sz[u] - (now > n);
	}
	//if (now > n) {
	//	assert(c[now].size() > 1);
	//	cout << "now " << now << ' ' << "sz " << sz[now] << ' ' << "apc " << apc << '\n';
	//	ll cur = c[now].size()-apc;
	//	res += cur * (c[now].size()-1) * (gsz-c[now].size());
	//	auto add = [&](ll a, ll b, ll all){
	//		cout << a << ' ' << b << ' ' << all-b << '\n';
	//		res += a * b * (all-b);
	//	};
	//	for (int u : tree_edge[now]) if(u != last) {
	//		add(cur, sz[u]-1, gsz);
	//	}
	//	add(c[now].size()-apc, gsz-sz[now], gsz);
	//	res += p3(cur);
	//}
	if (now > n){
		ll apc = 0;
		//cout << "now ";
		for (int u : c[now])
			apc += is_ap[u];//, cout << u << ' ';
		//cout << '\n';
		//cout << "sz " << sz[now] << '\n';
	ll ore = res;	
		auto add = [&](ll a_with_ap, ll b_with_ap, ll all) {
			//cout << a_with_ap << ' ' << b_with_ap << ' ' << all << '\n';
			//cout << (a_with_ap - apc) * (b_with_ap) * (a_with_ap - apc - 1) << '\n';
			res += (a_with_ap - apc) * (b_with_ap) * (a_with_ap - apc - 1) * 2;
			//cout << b_with_ap << ' ' << all - a_with_ap - b_with_ap + 1 << ' ' << a_with_ap - apc << '\n';
//			if (false)
//				cout  << "Y " << (b_with_ap) * (all - a_with_ap - b_with_ap + 1) * (a_with_ap - apc) << '\n';
			res += (b_with_ap) * (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());
		//res += (ll)(c[now].size()-1) * (ll)(c[now].size()-2) * apc;
		//cout << "all add " << res - ore << '\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);
	}
}
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';
}

Compilation message

count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:47:5: warning: unused variable 'ore' [-Wunused-variable]
  ll ore = res; 
     ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35576 KB Output is correct
2 Correct 26 ms 35576 KB Output is correct
3 Correct 25 ms 35576 KB Output is correct
4 Correct 25 ms 35448 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 25 ms 35448 KB Output is correct
7 Incorrect 26 ms 35576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35576 KB Output is correct
2 Correct 26 ms 35576 KB Output is correct
3 Correct 25 ms 35576 KB Output is correct
4 Correct 25 ms 35448 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 25 ms 35448 KB Output is correct
7 Incorrect 26 ms 35576 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 108 ms 49652 KB Output is correct
2 Correct 116 ms 49652 KB Output is correct
3 Correct 157 ms 56052 KB Output is correct
4 Correct 122 ms 50548 KB Output is correct
5 Correct 128 ms 51084 KB Output is correct
6 Correct 147 ms 57460 KB Output is correct
7 Correct 151 ms 51320 KB Output is correct
8 Correct 144 ms 54264 KB Output is correct
9 Correct 143 ms 49272 KB Output is correct
10 Correct 158 ms 49784 KB Output is correct
11 Correct 111 ms 44792 KB Output is correct
12 Correct 112 ms 44796 KB Output is correct
13 Correct 101 ms 44152 KB Output is correct
14 Correct 107 ms 44024 KB Output is correct
15 Correct 90 ms 42616 KB Output is correct
16 Correct 83 ms 42464 KB Output is correct
17 Correct 29 ms 36856 KB Output is correct
18 Correct 30 ms 36860 KB Output is correct
19 Correct 29 ms 36856 KB Output is correct
20 Correct 31 ms 36856 KB Output is correct
21 Correct 29 ms 36856 KB Output is correct
22 Correct 28 ms 36856 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 35704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 49784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 35832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 49656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35576 KB Output is correct
2 Correct 26 ms 35576 KB Output is correct
3 Correct 25 ms 35576 KB Output is correct
4 Correct 25 ms 35448 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 25 ms 35448 KB Output is correct
7 Incorrect 26 ms 35576 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35576 KB Output is correct
2 Correct 26 ms 35576 KB Output is correct
3 Correct 25 ms 35576 KB Output is correct
4 Correct 25 ms 35448 KB Output is correct
5 Correct 25 ms 35576 KB Output is correct
6 Correct 25 ms 35448 KB Output is correct
7 Incorrect 26 ms 35576 KB Output isn't correct
8 Halted 0 ms 0 KB -