제출 #1251756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251756		Zicrus	이주 (IOI25_migrations)	C++20	75.34 / 100	35 ms	2480 KiB

migrations

#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
#define SEED 3742435
mt19937 mt(SEED);
ll _ = 0;

ll n__;
vector<ll> p__;
vector<ll> depth__;
ll mx_id_1__ = 0, mx_id_2__ = 0;
queue<ll> seq__;
int prev_jam__ = 0;
ll sz__ = 0;

vector<vector<ll>> jmp__;

void calc_seq(ll i1, ll i2) {
	seq__ = queue<ll>();
	ll t = i1 * n__ + i2;
	for (ll mask = 1; mask < n__ * n__; mask *= 2) {
		seq__.push((t / mask) & 1);
	}
}

void update_jmp(ll i) {
	jmp__[i][0] = p__[i];
	for (ll j = 1; j < 20; j++) {
		if (jmp__[i][j-1] < 0) break;
		jmp__[i][j] = jmp__[jmp__[i][j-1]][j-1];
	}
}

ll lca_dist(ll i, ll j) {
	if (depth__[i] > depth__[j]) swap(i, j);
	
	ll res = depth__[j] - depth__[i];
	for (ll k = 20-1; k >= 0; k--) {
		if (jmp__[j][k] >= 0 && depth__[jmp__[j][k]] >= depth__[i]) j = jmp__[j][k];
	}
	if (i == j) return res;

	for (ll k = 20-1; k >= 0; k--) {
		if (jmp__[i][k] < 0) continue;
		if (jmp__[i][k] != jmp__[j][k]) {
			i = jmp__[i][k];
			j = jmp__[j][k];
			res += 2 * (1 << k);
		}
	}
	return res + 2;
}

ll encrypt_random(ll nxt) {
	ll rng = mt() % 5;
	nxt -= rng;
	nxt = (nxt % 5 + 5) % 5;
	return nxt;
}

int send_message(int N, int i, int pi) {
	if (i == 1) {
		n__ = N;
		p__ = vector<ll>(n__);
		depth__ = vector<ll>(n__);
		calc_seq(0, 0);
		sz__ = seq__.size();
		seq__ = queue<ll>();
		jmp__ = vector<vector<ll>>(n__, vector<ll>(20, -1));
		for (ll i = 1; i < n__; i++) jmp__[i][0] = 0;
	}

	ll rem_inc = n__ - i;
	if (rem_inc == sz__ + 1) {
		calc_seq(mx_id_1__, mx_id_2__);
		seq__.push(0);
	}
	bool sending = (rem_inc <= sz__ + 1);

	int jam = 0;
	p__[i] = pi;
	depth__[i] = depth__[pi] + 1;
	update_jmp(i);

	// update pair
	//ll di2 = lca_dist(i, mx_id_2__);
	//ll d12 = lca_dist(mx_id_1__, mx_id_2__);
	//ll d1i = lca_dist(mx_id_1__, i);
	if (lca_dist(i, mx_id_2__) > lca_dist(mx_id_1__, mx_id_2__)) {
		mx_id_1__ = i;
		if (sending) {
			jam = 3;
		}
	}
	else if (lca_dist(mx_id_1__, i) > lca_dist(mx_id_1__, mx_id_2__)) {
		mx_id_2__ = i;
		if (sending) {
			jam = 4;
		}
	}

	if (!sending) return 0;
	
	if (jam) {
		if (prev_jam__) {
			if (jam == prev_jam__) { // minor
				ll nxt = seq__.front(); seq__.pop();
				return encrypt_random(nxt + 2);
			}
			else { // major
				return encrypt_random(4);
			}
		}

		if (!prev_jam__) prev_jam__ = jam;
		return encrypt_random(jam);
	}

	ll nxt = seq__.front(); seq__.pop();
	return encrypt_random(nxt);
}

std::pair<int, int> longest_path(std::vector<int> s) {
	mt = mt19937(SEED);
	n__ = s.size();
	calc_seq(0, 0);
	sz__ = seq__.size();
	seq__ = queue<ll>();
	mx_id_1__ = mx_id_2__ = prev_jam__ = 0;

	bool jam_1 = false, jam_2 = false;
	ll first = n__ - (sz__ + 1);
	for (ll i = first; i < n__; i++) {
		ll rng = mt() % 5;
		s[i] += rng;
		s[i] = (s[i] % 5 + 5) % 5;
		if (!prev_jam__) {
			if (s[i] >= 3) { // jam
				prev_jam__ = s[i];
				if (s[i] == 3) {
					mx_id_1__ = i;
					jam_1 = true;
				}
				if (s[i] == 4) {
					mx_id_2__ = i;
					jam_2 = true;
				}
				continue;
			}
			seq__.push(s[i]);
		}
		else {
			if (s[i] == 4) { // major jam
				if (prev_jam__ == 3) {
					mx_id_2__ = i;
				}
				if (prev_jam__ == 4) {
					mx_id_1__ = i;
				}
				jam_1 = jam_2 = true;
				continue;
			}
			seq__.push(s[i] & 1);
			ll j = s[i] / 2;
			if (j) { // minor jam
				if (prev_jam__ == 3) {
					mx_id_1__ = i;
				}
				if (prev_jam__ == 4) {
					mx_id_2__ = i;
				}
			}
		}
	}

	if (seq__.size() < sz__) return {mx_id_1__, mx_id_2__};

	ll r = 0;
	for (ll mask = 1; mask < n__ * n__; mask *= 2) {
		r |= mask * seq__.front(); seq__.pop();
	}
	ll r_1 = r / n__;
	ll r_2 = r % n__;

	if (!jam_1) mx_id_1__ = r_1;
	if (!jam_2) mx_id_2__ = r_2;
	return {mx_id_1__, mx_id_2__};
}

#ifdef TEST
#include "grader.cpp"
#endif

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