Submission #498931

#	Time	Username	Problem	Language	Result	Execution time	Memory
498931		AdamGS	Speedrun (RMI21_speedrun)	C++14	100 / 100	2497 ms	988 KiB

speedrun

#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7;
vector<int>V[LIM], T;
int nxt[LIM], ojciec[LIM], odw[LIM];
void assignHints(int subtask, int n, int A[], int B[]) {
	rep(i, n-1) {
		V[A[i+1]-1].pb(B[i+1]-1);
		V[B[i+1]-1].pb(A[i+1]-1);
	}
	queue<int>q;
	q.push(0);
	while(!q.empty()) {
		int p=q.front(); q.pop();
		T.pb(p);
		for(auto i : V[p]) if(i!=ojciec[p]) {
			ojciec[i]=p;
			q.push(i);
		}
	}
	rep(i, n-1) nxt[T[i]]=T[i+1];
	setHintLen(20);
	rep(i, n) {
		rep(j, 10) setHint(i+1, j+1, (nxt[i]&(1<<j))==(1<<j));
		rep(j, 10) setHint(i+1, j+11, (ojciec[i]&(1<<j))==(1<<j));
	}
}
vector<int>znajdz(int n, int a, int b) {
	rep(i, n) ojciec[i]=-1;
	ojciec[a]=a;
	queue<int>q;
	q.push(a);
	while(!q.empty()) {
		int p=q.front(); q.pop();
		if(p==b) {
			vector<int>ans;
			while(ojciec[b]!=b) {
				ans.pb(b);
				b=ojciec[b];
			}
			reverse(all(ans));
			return ans;
		}
		for(auto i : V[p]) if(i!=ojciec[p]) {
			ojciec[i]=p;
			q.push(i);
		}
	}
}
int czytaj() {
	int ans=0;
	rep(i, 10) {
		int p=getHint(i+1);
		ans+=(1<<i)*p;
	}
	return ans;
}
void speedrun(int subtask, int n, int start) {
	--start;
	while(start) {
		int x=0;
		rep(i, 10) {
			int p=getHint(i+11);
			x+=(1<<i)*p;
		}
		goTo(x+1);
		start=x;
	}
	T.pb(0);
	odw[0]=1;
	T.pb(czytaj());
	int akt=0;
	rep(i, n-1) {
		while(!goTo(T[i+1]+1)) {
			vector<int>P=znajdz(n, T[akt], T[akt+1]);
			for(auto j : P) goTo(j+1);
			++akt;
		}
		V[T[i+1]].pb(T[akt]);
		V[T[akt]].pb(T[i+1]);
		T.pb(czytaj());
		if(i<n-2) goTo(T[akt]+1);
	}
}

Compilation message (stderr)

speedrun.cpp: In function 'std::vector<int> znajdz(int, int, int)':
speedrun.cpp:39:12: warning: control reaches end of non-void function [-Wreturn-type]
   39 |  queue<int>q;
      |            ^

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40