Submission #391516

#	Time	Username	Problem	Language	Result	Execution time	Memory
391516		patrikpavic2	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1105 ms	28128 KiB

meetings2

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 2e5 + 500;

vector < int > v[N], skp;

int boja[N], siz[N], ans[N], dep[N], bio[N];
int n, m;

void rootaj(int x, int lst, int cur = 0){
	boja[x] = cur; siz[x] = 1; 
	dep[x] = dep[lst] + 1;
	skp.PB(x);
	for(int y : v[x]){
		if(bio[y] || y == lst) continue;
		rootaj(y, x, cur ? cur : y);
		siz[x] += siz[y];
	}
}

int nadi_centroid(){
	int nn = (int)skp.size();
	int ret = skp[0];
	for(int x : skp)
		if(2 * siz[x] >= nn && siz[x] < siz[ret])
			ret = x;
	return ret;
}

inline void update(int x, int y){
	ans[x] = max(ans[x], y);
}

bool cmp(int x, int y){
	return siz[x] > siz[y];
}

void obradi(int x){
	rootaj(x, x, 0);
	x = nadi_centroid();
	skp.clear(); dep[x] = -1;
	rootaj(x, x, 0);
	int nn = (int)skp.size();
	for(int y : skp){
		if(y != x){
			update(min(siz[y], nn - siz[boja[y]]), dep[y]);
		}
	}
	skp.erase(find(skp.begin(), skp.end(), x));
	sort(skp.begin(), skp.end(), cmp);
	int naj = -1, najj = -1;
	for(int x : skp){
		if(naj == -1){
			naj = x; continue;
		}
		else if(najj == -1 && boja[x] != boja[naj]){
			najj = x;
		}
		else if(najj == -1 && boja[x] == boja[naj] && dep[x] > dep[naj]){
			naj = x; continue;
		}
		else if(najj == -1 && boja[x] == boja[naj]){
			continue;
		}
		else if(dep[x] > dep[naj] && boja[x] != boja[naj]){
			najj = naj; naj = x;
		}	
		else if(dep[x] > dep[naj] && boja[x] == boja[naj]){
			naj = x;
		}
		else if(dep[x] > dep[najj] && boja[x] != boja[naj]){
			najj = x;
		}
		update(min(siz[naj], siz[najj]), dep[naj] + dep[najj]);
	}
	skp.clear();
	bio[x] = 1;
	for(int y : v[x])
		if(!bio[y]) obradi(y);
}

int main(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	obradi(1);
	for(int i = n;i >= 0;i--)
		update(i, ans[i + 1]);
	for(int i = 1;i <= n;i++){
		printf("%d\n", (i & 1) ? 1 : ans[i / 2] + 1);
	}
	return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
meetings2.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

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