Submission #1262963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262963		gelastropod	Migrations (IOI25_migrations)	C++20	0 / 100	30 ms	1184 KiB

migrations

#include "migrations.h"

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

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;

int findE(int S, int E1, int E2) {
	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);
		}
	}
	if (d[E1] > d[E2]) return E1;
	return E2;
}

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);
		else E = findE(S, _i, bestes.second);
		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 (S == bestI) bestes = { S, E };
			else bestes = { E, S };
			return res;
		}
		if ((N - _i == 15 || N - _i == 7 || N - _i <= 5) && !(S == bestes.first && E == bestes.second) ){
			if (S != bestes.first && S != bestes.second)
				changeddiffS = N - _i;
			if (E != bestes.first && 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 (changeddiffS > 2 && changeddiffE > 2) return 0;
		if (changeddiffS > 2 && changeddiffE == 2) return 1;
		if (changeddiffS > 2 && changeddiffE == 1) return 2;
		if (changeddiffS == 1 && changeddiffE > 2) return 3;
		if (changeddiffS == 1 && changeddiffE == 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;
	}
	for (int i = N - 15; i < N; i++) {
		pair<int, int> crntans = { 0, 0 };
		if (S[N - 3] == 0) {
			for (int j = 0; j < 6; j++) {
				crntans.first += S[N - 15 + j * 2];
				crntans.first *= 5;
			}
		}
		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 - 7];
		}
		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 += S[N - 14 + j * 2];
				crntans.second *= 5;
			}
		}
		else if (S[N - 3] == 1) {
			crntans.second = N - 14 + S[N - 6] * 5 + S[N - 4];
		}
		else if (S[N - 3] == 2) {
			crntans.second = N - 6 + S[N - 6];
		}
		else if (S[N - 3] == 3) {
			crntans.second = N - 3;
		}
		else crntans.second = N - 2;
		if (S[N - 1] == 0)
			return crntans;
		if (S[N - 1] == 1)
			return { crntans.first, N - 2 };
		if (S[N - 1] == 2)
			return { crntans.first, N - 1 };
		if (S[N - 1] == 3)
			return { N - 1, crntans.second };
		return { N - 1, N - 2 };
	}
}

Compilation message (stderr)

migrations.cpp: In function 'std::pair<int, int> longest_path(std::vector<int>)':
migrations.cpp:160:1: warning: control reaches end of non-void function [-Wreturn-type]
  160 | }
      | ^

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