Submission #538205

#	Time	Username	Problem	Language	Result	Execution time	Memory
538205		pavement	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	14 ms	20696 KiB

meetings2

#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;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, md, fn, st, rt, sz[200005], osz[200005];
bool on_path[200005];
vector<int> path, adj[200005];
multiset<int> poss[200005];
priority_queue<ii, vector<ii>, greater<ii> > pq[200005];

void get_diam(int n, int e = -1, int d = 0) {
	if (d > md) {
		md = d;
		fn = n;
	}
	for (auto u : adj[n]) if (u != e) get_diam(u, n, d + 1);
}

bool get_path(int n, int e = -1) {
	if (n == fn) {
		on_path[n] = 1;
		path.pb(n);
		return 1;
	}
	for (auto u : adj[n]) if (u != e)
		if (get_path(u, n)) {
			on_path[n] = 1;
			path.pb(n);
			return 1;
		}
	return 0;
}

int dfs(int n, int e = -1, int d = 0) {
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e)
		sz[n] += dfs(u, n);
	pq[rt].emplace(sz[n], d);
	poss[rt].insert(d);
	return sz[n];
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	md = -1;
	get_diam(1);
	md = -1;
	st = fn;
	get_diam(st);
	// diameter is st --> fn
	get_path(st);
	for (int i = 1; i <= N; i++)
		if (on_path[i]) {
			sz[i] = 1;
			rt = i;
			for (auto u : adj[i])
				if (!on_path[u]) sz[i] += dfs(u, i);
			pq[i].emplace(sz[i], 0);
			poss[i].insert(0);
			osz[i] = sz[i];
		}
	reverse(path.begin(), path.end());
	for (int k = 1, ptr = 0, ptr2 = (int)path.size() - 1; k <= N; k++) {
		if (k & 1) cout << "1\n";
		else {
			if (sz[path[ptr]] == 0) ptr++;
			sz[path[ptr]]--;
			if (sz[path[ptr2]] == 0) ptr2--;
			sz[path[ptr2]]--;
			while (pq[path[ptr]].top().first < osz[path[ptr]] - sz[path[ptr]]) {
				poss[path[ptr]].erase(poss[path[ptr]].find(pq[path[ptr]].top().second));
				pq[path[ptr]].pop();
			}
			while (pq[path[ptr2]].top().first < osz[path[ptr2]] - sz[path[ptr2]]) {
				poss[path[ptr2]].erase(poss[path[ptr2]].find(pq[path[ptr2]].top().second));
				pq[path[ptr2]].pop();
			}
			cout << ptr2 - ptr + 1 + *poss[path[ptr]].rbegin() + *poss[path[ptr2]].rbegin() << '\n';
		}
	}
}

Compilation message (stderr)

meetings2.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main() {
      | ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80