oj.uz

Submission #498716

# Submission time Handle Problem Language Result Execution time Memory
498716 2021-12-26T08:48:05 Z amunduzbaev Speedrun (RMI21_speedrun) C++14
63 / 100
 310 ms 812 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(30);
	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);
		}
		
		for(int j=0;j<10;j++){
			setHint(i, j + 21, par[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);
		if(getHint(j + 21)) par |= (1 << j);
	}
	
	while(u == par && cur != u) 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 260 ms 676 KB Output is correct
2 Correct 298 ms 796 KB Output is correct
3 Correct 310 ms 668 KB Output is correct
4 Correct 245 ms 684 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 456 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 688 KB Output is correct
2 Correct 247 ms 812 KB Output is correct
3 Correct 236 ms 668 KB Output is correct
4 Correct 245 ms 796 KB Output is correct
5 Correct 268 ms 676 KB Output is correct
6 Correct 302 ms 668 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 289 ms 688 KB Partial solution
2 Partially correct 216 ms 660 KB Partial solution
3 Partially correct 273 ms 704 KB Partial solution
4 Partially correct 271 ms 668 KB Partial solution
5 Partially correct 190 ms 716 KB Partial solution
6 Partially correct 288 ms 696 KB Partial solution
7 Partially correct 247 ms 660 KB Partial solution