oj.uz

Submission #538054

# Submission time Handle Problem Language Result Execution time Memory
538054 2022-03-16T04:09:46 Z TaylorSwiftFangirl Speedrun (RMI21_speedrun) C++17
100 / 100
 205 ms 904 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;


int read(int place) {
	int ans = 0;
	for(int i=0; i<10; i++) {
		ans*=2;
		ans += getHint(place*10+i+1);
	}
	return ans;
}

void write(int x, int place, int v) {
	for(int i=0; i<10; i++) {
		setHint(x, place*10+i+1, v&(1<<(9-i)));
	}
}

 
vector<int> adj[1004], path;
void dfs(int x, int p) {
	path.push_back(x);
	write(x, 0, p);
	for(auto i : adj[x]) {
		if(i==p) continue;
		dfs(i, x);
	}
}
 
void assignHints(int st, int n, int a[], int b[]) {
	setHintLen(20);
	for(int i=1; i<n; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
    }	
	dfs(1, 0);
	for(int i=0; i<n-1; i++) {
		write(path[i], 1, path[i+1]);
	}
}

void speedrun(int st, int n, int start) {
	int curr = start;
	while(curr != 1) {
		int par = read(0);
		goTo(par);
		curr = par;
	}
	
	vector<int> depth{1};
	while(true) {
		int child = read(1);
		if(child == 0) break;
		if(goTo(child)) {
			depth.push_back(child);
		}
		else {
			while(true){
				depth.pop_back();
				goTo(depth.back());
				if(goTo(child)) {
					depth.push_back(child);
					break;
				}
			} 
		}
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 716 KB Output is correct
2 Correct 186 ms 804 KB Output is correct
3 Correct 178 ms 772 KB Output is correct
4 Correct 190 ms 904 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 756 KB Output is correct
2 Correct 169 ms 760 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 824 KB Output is correct
2 Correct 147 ms 796 KB Output is correct
3 Correct 166 ms 804 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 672 KB Output is correct
2 Correct 164 ms 708 KB Output is correct
3 Correct 192 ms 768 KB Output is correct
4 Correct 167 ms 744 KB Output is correct
5 Correct 183 ms 772 KB Output is correct
6 Correct 166 ms 808 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 736 KB Output is correct
2 Correct 140 ms 856 KB Output is correct
3 Correct 132 ms 704 KB Output is correct
4 Correct 167 ms 764 KB Output is correct
5 Correct 175 ms 724 KB Output is correct
6 Correct 122 ms 840 KB Output is correct
7 Correct 174 ms 748 KB Output is correct