oj.uz

Submission #504704

# Submission time Handle Problem Language Result Execution time Memory
504704 2022-01-10T07:46:30 Z minhcool Speedrun (RMI21_speedrun) C++17
100 / 100
 228 ms 908 KB 
#include<speedrun.h>
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e3 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n;
vector<int> Adj[N];
 
int cnt;
int l[N], r[N], pos[N];
int par[N];
vector<int> vc;
 
void dfs(int u, int p){
	cnt++;
	l[u] = pos[u] = cnt;
	vc.pb(u);
	for(auto v : Adj[u]){
		if(v == p) continue;
		par[v] = u;
		dfs(v, u);
	}
	r[u] = cnt;
}
 
void assignHints(int subtask, int N, int A[], int B[]){
	n = N;
	for(int i = 1; i < n; i++){
		Adj[A[i]].pb(B[i]);
		Adj[B[i]].pb(A[i]);
	}
	dfs(1, 1);
	setHintLen(20);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 10; j++){
			if(par[vc[i]] & (1LL << j)) setHint(vc[i], j + 1, 1);
			else setHint(vc[i], j + 1, 0);
		}
		int temp = vc[(i + 1) % n];
		for(int j = 0; j < 10; j++){
			if(temp & (1LL << j)) setHint(vc[i], j + 11, 1);
			else setHint(vc[i], j + 11, 0);
		}
	}
}
 
int get_par(){
	int ans = 0;
	for(int i = 0; i < 10; i++) if(getHint(i + 1)) ans += (1LL << i);
	return ans; 
}
 
int get_nxt(){
	int ans = 0;
	for(int i = 0; i < 10; i++) if(getHint(i + 11)) ans += (1LL << i);
	return ans;
}
 
void speedrun(int subtrask, int N, int start){
	int cur = start;
	for(int itr = 1; itr <= N; itr++){
		int nxt = get_nxt();
		if(nxt == 1){
			while(1){
				int temp = get_par();
				if(!temp) break;
				else goTo(temp);
			}
			continue;
		}
		while(1){
			if(goTo(nxt)) break;
			else goTo(get_par());
		}
	}
}
 
/*
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}*/

Compilation message

speedrun.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:74:6: warning: unused variable 'cur' [-Wunused-variable]
   74 |  int cur = start;
      |      ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 684 KB Output is correct
2 Correct 181 ms 672 KB Output is correct
3 Correct 207 ms 788 KB Output is correct
4 Correct 213 ms 680 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 712 KB Output is correct
2 Correct 118 ms 704 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 704 KB Output is correct
2 Correct 162 ms 660 KB Output is correct
3 Correct 153 ms 720 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 728 KB Output is correct
2 Correct 204 ms 700 KB Output is correct
3 Correct 228 ms 704 KB Output is correct
4 Correct 138 ms 800 KB Output is correct
5 Correct 192 ms 660 KB Output is correct
6 Correct 168 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 700 KB Output is correct
2 Correct 188 ms 676 KB Output is correct
3 Correct 110 ms 908 KB Output is correct
4 Correct 195 ms 660 KB Output is correct
5 Correct 203 ms 696 KB Output is correct
6 Correct 216 ms 680 KB Output is correct
7 Correct 162 ms 660 KB Output is correct