oj.uz

Submission #573091

# Submission time Handle Problem Language Result Execution time Memory
573091 2022-06-05T18:08:13 Z sidon Shymbulak (IZhO14_shymbulak) C++17
0 / 100
 41 ms 9828 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ii = array<int, 2>;

const int Z = 2e5;

int N, sz, vis[Z];
ii ans, cur, s[2*Z];
bool isR[Z];
vector<int> g[Z], st, h;

void dfs(int u, int p) {
	vis[u] = 2;
	st.push_back(u);

	for(int v : g[u]) if(v != p) {
		if(!empty(h)) return;

		if(vis[v] > 1) {
			while(st.back() != v) {
				h.push_back(st.back());
				st.pop_back();
			}
			h.push_back(v);
		} else if(!vis[v]) dfs(v, u);
	}
	if(!empty(st)) st.pop_back();

	vis[u] = 1;
}

ii comb(array<int, 2> x, array<int, 2> y) {
	if(x < y) swap(x, y);
	if(x[0] == y[0]) x[1] = x[1] + y[1];
	return x;
}

ii calc(int u, int p) {
	ii x = {0, 1}, y;
	for(int v : g[u]) if(v != p && !isR[v]) {
		y = calc(v, u);
		++y[0];
		ans = comb(ans, {x[0] + y[0], x[1] * y[1]});
		x = comb(x, y);
	}
	return x;
}

ii query(int l, int r) {
	ii x {-N};
	for(l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
		if(l & 1) x = comb(x, s[l++]);
		if(r & 1) x = comb(x, s[--r]);
	}
	return x;
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for(int i = N; i--; ) {
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(0, 0);
	sz = size(h);
	for(int u : h) isR[u] = 1;

	for(int i = sz; i--; ) {
		s[i+sz] = calc(h[i], -1);
		s[i+sz][0] += i;
	}

	for(int i = sz; --i; )
		s[i] = comb(s[2*i], s[2*i+1]);

	for(int i = sz; i--; ) {
		int j = i + (sz / 2) - 1;
		ii x = query(i+1, min(sz-1, j));
		x[0] -= i;
		if(j >= sz) {
			ii y = query(0, j - sz);
			y[0] += 1;
			x = comb(x, y);
		}
		x[0] += s[i+sz][0] - i;
		x[1] *= s[i+sz][1];
		ans = comb(ans, x);
	}

	cout << ans[1];
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9428 KB Output is correct
2 Incorrect 41 ms 9828 KB Output isn't correct
3 Halted 0 ms 0 KB -