제출 #1253353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253353		PanosPask	이주 (IOI25_migrations)	C++20	0 / 100	835 ms	1256 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> pi;

const int N = 10000;
const int logN = 14;
const int START = N - 2 * logN;
const int POINTS = 2;

vector<vector<int>> adj_list;

// Current endpoints of diameter
int id[POINTS] = {0, 0};
vector<int> d[POINTS];
bool swapped[POINTS] = {false, false};

void calculate_distance(int node, int par, vector<int>& d) {
	for (auto neigh : adj_list[node]) {
		if (neigh != par) {
			d[neigh] = d[node] + 1;
			calculate_distance(neigh, node, d);
		}
	}
}

pi find_max(vector<int>& d) {
	int opt = 0;
	for (int i = 0; i < N; i++) {
		if (d[i] > d[opt]) {
			opt = i;
		}
	}

	return mp(d[opt], opt);
}

pi find_time(int i) {
	return mp((i - START) % 2, (i - START) / 2);
}

int find_bit(int num, int b) {
	return (num & (1 << b)) != 0;
}

int send_message(int N, int i, int Pi) {
	if (i == 1) {
		adj_list.resize(N);
		d[0].resize(N);
		d[1].resize(N);
	}
	adj_list[i].pb(Pi);
	adj_list[Pi].pb(i);

	swapped[0] = swapped[1] = false;
	for (int p = 0; p < 2; p++) {
		d[p][id[p]] = 0;
		calculate_distance(id[p], -1, d[p]);
		pi res = find_max(d[p]);

		if (d[p][id[!p]] != res.first) {
			id[!p] = res.second;
			swapped[!p] = true;
			break;
		}
	}

	if (i >= START) {
		int p, step;
		tie(p, step) = find_time(i);

		int ans = 0;
		if (swapped[p]) {
			return 4;
		}
		if (swapped[!p]) {
			ans += 2;
		}

		ans += find_bit(id[p], step);

		return ans;
	}

	return 0;
}

pair<int, int> longest_path(vector<int> S) {
	id[0] = id[1] = 0;
	swapped[0] = swapped[1] = false;

	for (int i = START; i < N; i++) {
		int p, step;
		tie(p, step) = find_time(i);

		int ans = S[i];
		if (ans == 4) {
			id[p] = i;
			swapped[p] = true;
		}
		else {
			if (ans >= 2) {
				id[!p] = i;
				swapped[!p] = true;
			}
			if (!swapped[p]) {
				id[p] += (ans << step);
			}
		}
	}

	return mp(id[0], id[1]);
}

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