Submission #1263492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263492		gelastropod	Migrations (IOI25_migrations)	C++20	89.49 / 100	32 ms	1200 KiB

migrations

#include "migrations.h"
#include <vector>
#include <utility>
#include <queue>
#include <iostream>
using namespace std;

namespace self {
	int N = -1;
	vector<int> P = { 0 }, D = { 0 };
	vector<vector<int>> adjlist = { {} };
	int bestD = 0, bestI = 0, changeddiffS = 15, changeddiffE = 15;
	bool changed = false;
	pair<int, int> bestes = { 0, 0 };
	pair<int, int> mem;
}

using namespace self;

int findE(int S, int E1, int E2, int E3) {
	queue<int> bfs;
	vector<bool> visited(N, false);
	vector<int> d(N, -1);
	bfs.push(S);
	d[S] = 0;
	visited[S] = true;
	while (!bfs.empty()) {
		int i = bfs.front();
		bfs.pop();
		for (int j : adjlist[i]) {
			if (visited[j]) continue;
			visited[j] = true;
			d[j] = d[i] + 1;
			bfs.push(j);
		}
	}
	int maxd = *max_element(d.begin(), d.end());
	if (d[E1] == maxd) return E1;
	if (d[E2] == maxd) return E2;
	if (d[E3] == maxd) return E3;
	for (int i = 0; i < N; i++) if (d[i] == maxd) return i;
}

int send_message(int _N, int _i, int Pi) {
	if (N == -1) N = _N;
	changed = false;
	P.push_back(Pi);
	adjlist[Pi].push_back(_i);
	adjlist.push_back({ Pi });
	D.push_back(D[Pi] + 1);
	if (bestD < D[_i]) {
		bestI = _i;
		bestD = D[_i];
	}
	if (N - _i <= 15) {
		int S = bestI, E;
		if (S == _i) E = findE(S, bestes.first, bestes.second, bestes.second);
		else E = findE(S, _i, bestes.first, bestes.second);
		//)cout << S << ' ' << E << '\n';
		if (S > E) swap(S, E);
		if (N <= 15) {
			int res = 0;
			if (S == bestes.first && E == bestes.second) res = 0;
			else if ((S == _i && E == bestes.first) || (E == _i && S == bestes.first)) res = 2;
			else res = 1;
			if (res == 1) bestes.first = _i;
			else if (res == 2) bestes.second = _i;
			return res;
		}
		if ((N - _i == 15 || N - _i == 7 || N - _i <= 5) && !(S == bestes.first && E == bestes.second) ){
			if (S != bestes.first && E != bestes.first)
				changeddiffS = N - _i;
			if (S != bestes.second && E != bestes.second)
				changeddiffE = N - _i;
			if (S == bestes.first || E == bestes.second) bestes = { S, E };
			else bestes = { E, S };
		}
		if (N - _i > 3) {
			int digit = (N - _i - 4) / 2;
			if ((N - _i) % 2) {
				int S = bestes.first;
				if (changeddiffS == 7) S -= (N - 14);
				if (changeddiffS == 5) S -= (N - 6);
				for (int i = 0; i < digit; i++, S /= 5);
				return S % 5;
			}
			else {
				int E = bestes.second;
				if (changeddiffE == 7) E -= (N - 14);
				if (changeddiffE <= 5) E -= (N - 6);
				for (int i = 0; i < digit; i++, E /= 5);
				return E % 5;
			}
		}
		if (N - _i == 3) {
			if (changeddiffS == 15) return 0;
			if (changeddiffS == 7) return 1;
			return 7 - changeddiffS;
		}
		if (N - _i == 2) {
			if (changeddiffE == 15) return 0;
			if (changeddiffE == 7) return 1;
			if (changeddiffE == 5) return 2;
			return 6 - changeddiffE;
		}
		if (changeddiffE >= 2 && changeddiffS > 2) return 0;
		if (changeddiffE >= 2 && changeddiffS == 2) return 1;
		if (changeddiffE >= 2 && changeddiffS == 1) return 2;
		if (changeddiffE == 1 && changeddiffS > 2) return 3;
		if (changeddiffE == 1 && changeddiffS == 2) return 4;
	}
	return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
	int N = S.size(), cnt = 0;
	if (N <= 15) {
		pair<int, int> crntans = { 0, 0 };
		for (int i : S) {
			if (i == 1) crntans.first = cnt;
			if (i == 2) crntans.second = cnt;
			cnt++;
		}
		return crntans;
	}
		pair<int, int> crntans = { 0, 0 };
		if (S[N - 3] == 0) {
			for (int j = 0; j < 6; j++) {
				crntans.first *= 5;
				crntans.first += S[N - 15 + j * 2];
			}
		}
		else if (S[N - 3] == 1) {
			crntans.first = N - 14 + S[N - 7] * 5 + S[N - 5];
		}
		else if (S[N - 3] == 2) {
			crntans.first = N - 6 + S[N - 5];
		}
		else if (S[N - 3] == 3) {
			crntans.first = N - 4;
		}
		else crntans.first = N - 3;
		if (S[N - 2] == 0) {
			for (int j = 0; j < 6; j++) {
				crntans.second *= 5;
				crntans.second += S[N - 14 + j * 2];
			}
		}
		else if (S[N - 2] == 1) {
			crntans.second = N - 14 + S[N - 6] * 5 + S[N - 4];
		}
		else if (S[N - 2] == 2) {
			crntans.second = N - 6 + S[N - 4];
		}
		else if (S[N - 2] == 3) {
			crntans.second = N - 3;
		}
		else crntans.second = N - 2;
		if (S[N - 1] == 0)
			return crntans;
		if (S[N - 1] == 1)
			return { crntans.second, N - 2 };
		if (S[N - 1] == 2)
			return { crntans.second, N - 1 };
		if (S[N - 1] == 3)
			return { N - 1, crntans.first };
		return { N - 1, N - 2 };
}

Compilation message (stderr)

migrations.cpp: In function 'int findE(int, int, int, int)':
migrations.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

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