oj.uz

Submission #536991

# Submission time Handle Problem Language Result Execution time Memory
536991 2022-03-14T08:57:09 Z zaneyu Speedrun (RMI21_speedrun) C++14
100 / 100
 196 ms 936 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define unq(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const int maxn=2e3+5;
using namespace std;
vector<int> v[maxn];
vector<int> vv;
void dfs(int u,int p){
	REP(j,10) setHint(u,j+1,(p&(1<<j))>>j);
	if(u>1){
		v[u].erase(find(ALL(v[u]),p));
	}
	vv.pb(u);
	REP(j,sz(v[u])){
		int x=v[u][j];
		int nxt=u;
		dfs(x,u);
	}
}
void assignHints(int subtask, int n, int A[], int B[]) {
	setHintLen(20);
	REP1(i,n-1){
		v[A[i]].pb(B[i]);
		v[B[i]].pb(A[i]);
	}
	dfs(1,1023);
	REP(i,n-1){
		REP(j,10) setHint(vv[i],j+11,(vv[i+1]&(1<<j))>>j);
	}
}
void speedrun(int subtask, int n, int start) {
	while(start!=1){
		int p=0;
		REP(j,10) p=(p<<1)+getHint(10-j);
		goTo(p);
		start=p;
	}
	REP(i,n-1){
		int nxt=0;
		REP(j,10) nxt=(nxt<<1)+getHint(20-j);
		while(!goTo(nxt)){
			int p=0;
			REP(j,10) p=(p<<1)+getHint(10-j);
			goTo(p);
		}
	}
}

Compilation message

speedrun.cpp: In function 'void dfs(int, int)':
speedrun.cpp:24:7: warning: unused variable 'nxt' [-Wunused-variable]
   24 |   int nxt=u;
      |       ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 696 KB Output is correct
2 Correct 196 ms 864 KB Output is correct
3 Correct 185 ms 896 KB Output is correct
4 Correct 110 ms 936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 748 KB Output is correct
2 Correct 173 ms 764 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 884 KB Output is correct
2 Correct 155 ms 756 KB Output is correct
3 Correct 178 ms 804 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 868 KB Output is correct
2 Correct 181 ms 760 KB Output is correct
3 Correct 128 ms 852 KB Output is correct
4 Correct 157 ms 920 KB Output is correct
5 Correct 181 ms 684 KB Output is correct
6 Correct 118 ms 868 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 740 KB Output is correct
2 Correct 184 ms 676 KB Output is correct
3 Correct 178 ms 836 KB Output is correct
4 Correct 165 ms 776 KB Output is correct
5 Correct 163 ms 740 KB Output is correct
6 Correct 187 ms 816 KB Output is correct
7 Correct 172 ms 712 KB Output is correct