oj.uz

Submission #498931

# Submission time Handle Problem Language Result Execution time Memory
498931 2021-12-26T18:46:37 Z AdamGS Speedrun (RMI21_speedrun) C++14
100 / 100
 2497 ms 988 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 736 KB Output is correct
2 Correct 298 ms 744 KB Output is correct
3 Correct 279 ms 720 KB Output is correct
4 Correct 817 ms 692 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 656 KB Output is correct
2 Correct 208 ms 724 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 824 KB Output is correct
2 Correct 2497 ms 988 KB Output is correct
3 Correct 1637 ms 968 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 792 KB Output is correct
2 Correct 134 ms 780 KB Output is correct
3 Correct 169 ms 684 KB Output is correct
4 Correct 613 ms 836 KB Output is correct
5 Correct 268 ms 780 KB Output is correct
6 Correct 174 ms 668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 716 KB Output is correct
2 Correct 234 ms 788 KB Output is correct
3 Correct 226 ms 724 KB Output is correct
4 Correct 368 ms 668 KB Output is correct
5 Correct 200 ms 660 KB Output is correct
6 Correct 288 ms 908 KB Output is correct
7 Correct 168 ms 804 KB Output is correct