oj.uz

Submission #538533

# Submission time Handle Problem Language Result Execution time Memory
538533 2022-03-17T04:09:00 Z ddy888 Speedrun (RMI21_speedrun) C++17
100 / 100
 177 ms 984 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];
vector<int> path;

void setchild(int u, int v) {
	int tmp = v, bit = 1;
	while (tmp) {
		setHint(u, bit, tmp % 2);
		tmp /= 2;
		++bit;
	}
}

void setpar(int u, int v) {
	int tmp = v, bit = 11;
	while (tmp) {
		setHint(u, bit, tmp % 2);
		tmp /= 2;
		++bit;
	}
}

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

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

void dfs(int x, int p) {
	if (path.size()) {
		setchild(path.back(), x);
		setpar(x, p);
	}
	path.pb(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 */
	set<int> vis;
	vis.insert(start);
	while ((int)vis.size() != _N) {
		int node = getchild();
		if (node == 0) {
			while (node != 1) {
				node = getpar();
				goTo(node);
				vis.insert(node);
			}
		} else {
			while (!goTo(node)) {
				vis.insert(getpar());
				goTo(getpar());
			}
		}
		vis.insert(node);
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 844 KB Output is correct
2 Correct 141 ms 920 KB Output is correct
3 Correct 174 ms 672 KB Output is correct
4 Correct 163 ms 984 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 720 KB Output is correct
2 Correct 156 ms 776 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 748 KB Output is correct
2 Correct 168 ms 788 KB Output is correct
3 Correct 177 ms 948 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 952 KB Output is correct
2 Correct 158 ms 676 KB Output is correct
3 Correct 167 ms 748 KB Output is correct
4 Correct 111 ms 876 KB Output is correct
5 Correct 159 ms 804 KB Output is correct
6 Correct 155 ms 892 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 728 KB Output is correct
2 Correct 168 ms 784 KB Output is correct
3 Correct 172 ms 780 KB Output is correct
4 Correct 133 ms 868 KB Output is correct
5 Correct 169 ms 796 KB Output is correct
6 Correct 137 ms 772 KB Output is correct
7 Correct 158 ms 776 KB Output is correct