Submission #386291

#	Time	Username	Problem	Language	Result	Execution time	Memory
386291		model_code	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	580 ms	50796 KiB

meetings2

#include <bits/stdc++.h>
#define SIZE 200005
#define BT 21
using namespace std;
typedef pair <int, int> P;

vector <int> vec[SIZE];
vector <int> vt[SIZE];
int nd[SIZE], ans[SIZE];
P centroid(int v, int p, int all) {
	P ret = P(all, v);
	int mx = 0;
	nd[v] = 1;
	for(int i=0; i < vec[v].size(); i++) {
		int to = vec[v][i];
		if(to != p) {
			ret = min(ret, centroid(to, v, all));
			nd[v] += nd[to];
			mx = max(mx, nd[to]);
		}
	}
	mx = max(mx, all - nd[v]);
	ret = min(ret, P(mx, v));
	return ret;
}
int par[SIZE][BT], dep[SIZE];
void dfs(int v, int p, int d) {
	dep[v] = d;
	par[v][0] = p;
	nd[v] = 1;
	for(int i = 0; i < vec[v].size(); i++) {
		int to = vec[v][i];
		if(to != p) {
			dfs(to, v, d + 1);
			nd[v] += nd[to];
		}
	}
}
void build(int n) {
	for(int i = 0; i + 1 < BT; i++) {
		for(int j = 0; j < n; j++) {
			if(par[j][i] != -1) par[j][i + 1] = par[par[j][i]][i];
			else par[j][i + 1] = -1;
		}
	}
}
int LCA(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	for(int i = BT - 1; i >= 0; i--) {
		if(par[b][i] != -1 && dep[par[b][i]] >= dep[a]) b = par[b][i];
	}
	if(a == b) return a;
	for(int i = BT - 1; i >= 0; i--) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i], b = par[b][i];
		}
	}
	return par[a][0];
}
int dist(int a, int b) {
	return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
}
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--, b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	int rt = centroid(0, -1, n).second;
	dfs(rt, -1, 0);
	build(n);
	for(int i = 0; i < n; i++) vt[nd[i]].push_back(i);
	int a = rt, b = rt, c = 0;
	for(int i = n / 2; i >= 1; i--) {
		for(int j = 0; j < vt[i].size(); j++) {
			int v = vt[i][j];
			int d = dist(a, v), e = dist(b, v);
			if(c < d) b = v, c = d;
			else if(c < e) a = v, c = e;
		}
		ans[i] = c;
	}
	for(int i = 1; i <= n; i++) {
		if(i % 2 == 1) printf("%d\n", 1);
		else printf("%d\n", ans[i / 2] + 1);
	}
}

Compilation message (stderr)

meetings2.cpp: In function 'P centroid(int, int, int)':
meetings2.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0; i < vec[v].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs(int, int, int)':
meetings2.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < vec[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int j = 0; j < vt[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
meetings2.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
meetings2.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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