제출 #249987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249987		srvlt	관광지 (IZhO14_shymbulak)	C++14	0 / 100	65 ms	23416 KiB

shymbulak

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2e5 + 123;
int n, used[n0], par[n0], k, c[n0], inc[n0], h[n0];
vector <int> g[n0];

void dfs(int v, int p) {
	used[v] = 1;
	for (int to : g[v]) {
		if (to == p) continue;
		if (used[to] == 1) {
			int u = v;
			while (u != to) {
				c[++k] = u, inc[u] = 1;
				u = par[u];
			}
			c[++k] = to, inc[to] = 1;
		}
		if (used[to] == 0) {
			par[to] = v;
			dfs(to, v);
		}
	}
	used[v] = 2;
}

struct Pair {
	int x, y;
	Pair(int X = 0, int Y = 0) {
		x = X, y = Y;
	}
};

Pair max(const Pair & p1, const Pair & p2) {
	if (p1.x > p2.x) return p1;
	if (p2.x > p1.x) return p2;
	return Pair(p1.x, p1.y + p2.y);
}
Pair b[n0];
ll cnt[n0];

void go(int v, int p) {
	b[v] = Pair(h[v], 1);
	for (int to : g[v]) {
		if (inc[to] || to == p) continue;
		h[to] = h[v] + 1;
		go(to, v);
		b[v] = max(b[v], b[to]);
	}
}

struct Node {
	int l = 0, r = 0;
	Pair x, y;
	void clean() {
		x.x = -n0, x.y = 0;
		y.x = -n0, y.y = 0;
	}
	void init() {
		x = Pair(b[c[l]].x - l, b[c[l]].y);
		y = Pair(b[c[l]].x + l, b[c[l]].y);
	}
	void merge(const Node & L, const Node & R) {
		x = max(L.x, R.x);
		y = max(L.y, R.y);
	}
};
Node t[1 << 19];

void build(int v, int l, int r) {
	t[v].l = l, t[v].r = r;
	if (l == r) {
		t[v].init();
		return;
	}
	int m = l + r >> 1;
	build(v << 1, l, m), build(v << 1 | 1, m + 1, r);
	t[v].merge(t[v << 1], t[v << 1 | 1]);
}

Node res;
void get(int v, int l, int r) {
	if (t[v].l > r || t[v].r < l) return;
	if (t[v].l >= l && t[v].r <= r) {
		res.merge(res, t[v]);
		return;
	}
	get(v << 1, l, r), get(v << 1 | 1, l, r);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb(y), g[y].pb(x);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++)
		if (inc[i]) go(i, i);
	build(1, 1, k);
	//cerr << "k " << k << '\n';
	//for (int i = 1; i <= k; i++) cerr << c[i] << ' ';
	//cerr << '\n';
	//for (int i = 1; i <= k; i++) {
		//cerr << b[c[i]].x << ' ' << b[c[i]].y;
		//if (i < k) cerr << ", ";
	//}
	//cerr << '\n';
	for (int i = 1; i <= k; i++) {
		int l = i + k / 2 + 1, r = k;
		//cerr << "i " << i << '\n';
		if (l <= r) {
			//cerr << "l r " << l << ' ' << r << '\n';
			res.clean(), get(1, l, r);
			if (res.x.x != -n0) {
				//cerr << "d " << res.x.x + (k + b[c[i]].x + i) << ' ' << (ll)2 * res.x.y * b[c[i]].y << '\n';
				cnt[res.x.x + (k + b[c[i]].x + i)] += (ll)2 * res.x.y * b[c[i]].y;
			}
		}
		l = i + 1, r = min(k, i + k / 2);
		if (l <= r) {
			//cerr << "l r " << l << ' ' << r << '\n';
			res.clean(), get(1, l, r);
			if (res.y.x != -n0) {
				//cerr << "d " << res.y.x + (b[c[i]].x - i) << ' ' << (ll)2 * res.y.y * b[c[i]].y << '\n';
				//cerr << "res " << res.y.x << ' ' << res.y.y << '\n';
				cnt[res.y.x + (b[c[i]].x - i)] += (ll)2 * res.y.y * b[c[i]].y;
			}
		}
	}
	for (int i = n; i > 0; i--)
		if (cnt[i]) return cout << cnt[i], 0;
}

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'void build(int, int, int)':
shymbulak.cpp:87:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50