Submission #1254867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254867		PenguinsAreCute	Migrations (IOI25_migrations)	C++20	89.49 / 100	37 ms	1484 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

int h[10'005], j[10'005], p[10'005];
int d0[10'005], d1[10'005];
int lca(int x, int y) {
	if(h[x] > h[y])
		swap(x, y);
	while(h[y] > h[x])
		y = (h[j[y]]<h[x]?p[y]:j[y]);
	while(x != y) {
		if(j[x] == j[y])
			x = p[x], y = p[y];
		else
			x = j[x], y = j[y];
	}
	return x;
}
int dist(int x, int y) {
	return h[x] + h[y] - 2 * h[lca(x,y)];
}

vector<vector<int>> res;
void gen(int l, int u, vector<int> cur) {
	if(cur.empty())
		res.clear();
	int cnt = 0;
	for(auto i: cur)
		cnt += !!i;
	if(cnt > u)
		return;
	if(cur.size() == l) {
		res.push_back(cur);
		return;
	}
	for(int i=0;i<5;i++) {
		cur.push_back(i);
		gen(l,u,cur);
		cur.pop_back();
	}
}

int send_message(int N, int i, int Pi) {
	h[i] = h[Pi] + 1;
	p[i] = Pi;
	j[i] = (h[Pi]+h[j[j[Pi]]]==2*h[j[Pi]]?j[j[Pi]]:Pi);
	d0[i] = d0[i-1];
	d1[i] = d1[i-1];
	if(dist(d0[i],i) > dist(d0[i],d1[i]))
		d1[i] = i;
	if(dist(i,d1[i]) > dist(d0[i],d1[i]))
		d0[i] = i;

	if(i < N - 29)
		return 0;
	if(i == N - 29)
		gen(11, 3, {});
	if(i >= N - 29 && i <= N - 19)
		return res[d0[N-29]][i-(N-29)];
	if(i >= N - 18 && i <= N - 8)
		return res[d1[N-18]][i-(N-18)];
	if(i == N - 7)
		gen(2, 2, {});
	if(i >= N - 7 && i <= N - 6)
		return (d0[N-29]==d0[N-7]?0:res[d0[N-7]-(N-29)][i-(N-7)]);
	if(i >= N - 5 && i <= N - 4)
		return (d1[N-18]==d1[N-5]?0:res[d1[N-5]-(N-18)][i-(N-5)]);
	if(i == N - 3)
		return (d0[N-7]==d0[N-3]?0:d0[N-3]-(N-7));
	if(i == N - 2)
		return (d1[N-2]==d1[N-5]?0:d1[N-2]-(N-5));
	if(i == N - 1) {
		int x = (d0[N-3]==d0[N-1]?0:d0[N-1]-(N-3));
		int y = (d1[N-2]==d1[N-1]?0:1);
		return 2 * x + y;
	}
	assert(0);
}

std::pair<int, int> longest_path(std::vector<int> S) {
	int N = S.size();
	gen(11, 3, {});
	vector<int> V(S.end()-29,S.end()-18);
	int d0 = lower_bound(res.begin(),res.end(),V)-res.begin();
	V = vector<int>(S.end()-18,S.end()-7);
	int d1 = lower_bound(res.begin(),res.end(),V)-res.begin();
	gen(2, 2, {});
	V = vector<int>(S.end()-7,S.end()-5);
	int nw = lower_bound(res.begin(),res.end(),V)-res.begin();
	if(nw)
		d0 = N - 29 + nw;
	V = vector<int>(S.end()-5,S.end()-3);
	nw = lower_bound(res.begin(),res.end(),V)-res.begin();
	if(nw)
		d1 = N - 18 + nw;
	if(S[N-3])
		d0 = N - 7 + S[N-3];
	if(S[N-2])
		d1 = N - 5 + S[N-2];
	int x = S[N-1]/2, y = S[N-1]%2;
	if(x)
		d0 = N - 3 + x;
	if(y)
		d1 = N - 1;
	return {d0,d1};
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 59.4934 / 70