Submission #1314741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314741		marcogambaro	Migrations (IOI25_migrations)	C++20	30 / 100	28 ms	1224 KiB

migrations

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

vector<int> d(200073);
int f = 0;

int send_message(int N, int i, int Pi) {
	d[i] = d[Pi]+1;
	bool nw = 0;

	if(d[i] > d[f]) {
		nw = 1;
		f = i;
	}

	int n = N-1 - i;
	if(n > 14) return 0;
	
	if(nw) return 2;
	else if(f & (1 << n)) return 1;
	return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
	int N = S.size();
	
	for(int i=0; i<=14; i++) {
		if(S[N-1-i] == 1) f += (1 << i);
		else if(S[N-1-i] == 2) return {0, N-1-i};
	}

	return {0, f};
}

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