oj.uz

Submission #498717

# Submission time Handle Problem Language Result Execution time Memory
498717 2021-12-26T08:50:47 Z amunduzbaev Speedrun (RMI21_speedrun) C++14
100 / 100
 278 ms 908 KB 
#include "speedrun.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

void assignHints(int subtask, int n, int a[], int b[]) {
	vector<vector<int>> edges(n + 1);
	vector<int> par(n + 1), tt, nxt(n + 1);
	for(int i=1;i<n;i++){
		edges[a[i]].push_back(b[i]);
		edges[b[i]].push_back(a[i]);
	}
	
	function<void(int, int)> dfs = [&](int u, int p){
		tt.push_back(u), par[u] = p;
		for(auto x : edges[u]){
			if(x == p) continue;
			dfs(x, u);
		}
	};
	
	dfs(1, 1);
	int p = 0;
	for(auto x : tt) nxt[p] = x, p = x;
	nxt[p] = 1;
	
	setHintLen(20);
	for(int i=1;i<=n;i++){
		for(int j=0;j<10;j++){
			setHint(i, j + 1, par[i]>>j&1);
		}
		
		for(int j=0;j<10;j++){
			setHint(i, j + 11, nxt[i]>>j&1);
		}
	}
}

int cur; //, par;

void dfs(int u, int p = -1){
	cur = 0; // , par = 0;
	for(int j=0;j<10;j++){
		if(getHint(j + 11)) cur |= (1 << j);
	}
	
	while(cur != p && goTo(cur)) dfs(cur, u);
	if(~p) goTo(p);
}

void speedrun(int subtask, int n, int u) {
	while(u != 1){
		int par = 0;
		for(int j=0;j<10;j++) par |= (getHint(j + 1) << j);
		goTo(par), u = par;
	}
	
	dfs(u);
}

/*

5
1 2
2 3
3 4
4 5
1

*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 788 KB Output is correct
2 Correct 191 ms 700 KB Output is correct
3 Correct 217 ms 748 KB Output is correct
4 Correct 203 ms 780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 680 KB Output is correct
2 Correct 227 ms 660 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 788 KB Output is correct
2 Correct 155 ms 820 KB Output is correct
3 Correct 232 ms 804 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 800 KB Output is correct
2 Correct 278 ms 660 KB Output is correct
3 Correct 199 ms 664 KB Output is correct
4 Correct 166 ms 660 KB Output is correct
5 Correct 191 ms 676 KB Output is correct
6 Correct 184 ms 788 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 676 KB Output is correct
2 Correct 190 ms 660 KB Output is correct
3 Correct 188 ms 704 KB Output is correct
4 Correct 180 ms 908 KB Output is correct
5 Correct 229 ms 680 KB Output is correct
6 Correct 169 ms 680 KB Output is correct
7 Correct 166 ms 788 KB Output is correct