Submission #551722

#	Time	Username	Problem	Language	Result	Execution time	Memory
551722		GioChkhaidze	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	594 ms	74756 KiB

meetings2

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 2e5 + 5;

int n;
int timer, in[N], out[N], dep[N], tot[N], ans[N], P[N][20];
vector < int > v[N];
set < int > st[N];

bool is_anc(int a, int b) {
	return (in[a] <= in[b] && out[b] <= out[a]);
}

int LCA(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	if (is_anc(a, b)) return a;
	for (int j = 18; j >= 0; --j) 
		if (!is_anc(P[a][j], b)) a = P[a][j];
	return P[a][0];
}

int dst(int a, int b) {
	return dep[a] + dep[b] - 2 * dep[LCA(a, b)] + 1;
}

void dfs(int x, int p) {
	dep[x] = dep[p] + 1;
	in[x] = ++timer;
	P[x][0] = p;
	for (int j = 1; j <= 18; ++j) {
		P[x][j] = P[P[x][j - 1]][j - 1];
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
	}
	out[x] = timer;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
		st[a].insert(b);
		st[b].insert(a);
	}
	
	dfs(1, 1);
	set < pair < int , int > > S;
	for (int i = 1; i <= n; ++i) {
		tot[i] = 1;
		if (v[i].size() == 1) {
			S.insert({tot[i], i});
		}
	}
	
	vector < pair < int , int > > rec;
	while (S.size()) {
		int x = (*S.begin()).s;
		S.erase(S.find(*S.begin()));
		if (st[x].size() == 1) {
			int y = (*st[x].begin());
			rec.pb({x, tot[x]});
			tot[y] += tot[x];
			st[y].erase(st[y].find(x));
			st[x].erase(st[x].find(y));
			if (st[y].size() == 1) {
				S.insert({tot[y], y});
			}
		}
	}
	
	int str = 1;
	for (int i = 1; i <= n; ++i) {
		if (tot[i] == n) str = i;
	}
	
	int a0 = str, b0 = str, dm = 1;
	for (int i = n; i >= 1; --i) {
		if (i % 2 == 1) {
			ans[i] = 1;
		}
			else {
			while (rec.size() && rec.back().s >= i / 2) {
				int x = rec.back().f, a1 = dst(a0, x), b1 = dst(b0, x);
				rec.pop_back();
				if (a1 <= b1) {
					if (dm < b1) dm = b1, a0 = x;
				}
					else 
				if (b1 < a1) {
					if (dm < a1) dm = a1, b0 = x;
				}
			}
			ans[i] = dm;		
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << "\n";
	} 
}

Compilation message (stderr)

meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
meetings2.cpp: At global scope:
meetings2.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main () {
      | ^~~~

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