oj.uz

Submission #538496

# Submission time Handle Problem Language Result Execution time Memory
538496 2022-03-17T03:18:56 Z ddy888 Speedrun (RMI21_speedrun) C++17
0 / 100
 52 ms 780 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#include "speedrun.h"

int N, lst;
vector<int> adj[1010];

void init(int x, int p) {
	int tmp = x, bit = 1;
	while (tmp != 0) {
		if (tmp % 2) setHint(p, bit, 1);
		++bit;
		tmp /= 2;
	}
}

int getval() {
	int ret = 0;
	for (int i = 1; i <= 20; ++i) {
		if (getHint(i) == 1) ret += (1 << (i - 1));
	}
	return ret;
}

void dfs(int x, int p) {
	if (x != 1) init(x, lst); // lst -> x
	lst = x;
	for (auto i: adj[x]) {
		if (i == p) continue;
		dfs(i, x);
	}
}
	
void assignHints(int subtask, int _N, int A[], int B[]) { /* your solution here */
	N = _N;
	for (int i = 1; i < N; ++i) {
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	setHintLen(20);	
	dfs(1, 1);	
}

void speedrun(int subtask, int _N, int start) { /* your solution here */
	vector<int> path;
	set<int> vis;
	path.pb(start);
	vis.insert(start);
	int node = start;
	while (1) {
		node = getval();
		while (!goTo(node)) { // backtrack
			goTo(path.back());
			path.pop_back();
		}
		path.pb(node);
		vis.insert(node);
		if ((int)vis.size() == N) break;
	}
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 672 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 696 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 748 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 780 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 676 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -