oj.uz

Submission #498711

# Submission time Handle Problem Language Result Execution time Memory
498711 2021-12-26T08:41:47 Z amunduzbaev Speedrun (RMI21_speedrun) C++14
0 / 100
 936 ms 788 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;

void dfs(int u, int p = -1){
	int x = 0;
	for(int j=0;j<10;j++) x |= (getHint(j + 11) << j);
	cur = x;
	while(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
3 5
1

*/

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 660 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 660 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 788 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 936 ms 780 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 676 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -