| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 504687 | hollwo_pelw | Speedrun (RMI21_speedrun) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
if (fopen(filein.c_str(), "r")){
freopen(filein.c_str(), "r", stdin);
freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
freopen(fileerr.c_str(), "w", stderr);
#endif
}
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}
void Hollwo_Pelw();
#ifdef hollwo_pelw_local
signed main(){
FAST_IO("input.inp", "output.out", "error.err");
auto start = chrono::steady_clock::now();
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
auto end = chrono::steady_clock::now();
cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
return 0;
}
#endif
const int N = 1005;
vector<int> adj[N];
#ifdef hollwo_pelw_local
namespace interactive {
int hint[N], size, fail_cnt, curnode;
void setHintLen(int l) {
size = l, fail_cnt = 0;
}
void setHint(int i, int j, bool b) {
assert(1 <= j && j <= size);
if (b) hint[i] |= 1 << j - 1;
}
int getLength() {
return size;
}
bool getHint(int j) {
assert(1 <= j && j <= size);
return hint[curnode] >> (j - 1) & 1;
}
bool goTo(int x) {
for (auto v : adj[curnode])
if (v == x) {
curnode = v;
return 1;
}
++ fail_cnt;
if (fail_cnt > 2000)
assert(0);
return 0;
}
}
using namespace interactive;
#endif
vector<int> ord;
int par[N];
void pre_dfs(int u, int p) {
ord.push_back(u);
par[u] = p;
for (auto v : adj[u]) if (v != p) {
pre_dfs(v, u);
}
}
void assignHints(int subtask, int N, int A[], int B[]) {
for (int i = 1; i < N; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
setHintLen(20);
pre_dfs(1, 0);
ord.push_back(0);
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 10; j++)
if (par[i] >> j & 1)
setHint(i, j + 1, 1);
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 10; j++)
if (ord[i] >> j & 1)
setHint(ord[i - 1], j + 11, 1);
}
}
inline int getpar() {
int res = 0;
for (int i = 0; i < 10; i++)
if (getHint(i + 1))
res |= 1 << i;
return res;
}
inline int getnxt() {
int res = 0;
for (int i = 0; i < 10; i++)
if (getHint(i + 11))
res |= 1 << i;
return res;
}
void speedrun(int subtask, int N, int start) {
int cur = start;
while (int p = getpar()) {
if (goTo(p)) cur = p;
}
while (int nxt = getnxt()) {
if (!nxt) return ;
while (!goTo(nxt))
if (goTo(getpar()))
cur = getpar();
cur = nxt;
}
}
void Hollwo_Pelw() {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N; cin >> N;
int A[N], B[N];
for (int i = 1; i < N; i++)
cin >> A[i] >> B[i];
assignHints(1, N, A, B);
speedrun(1, N, curnode = rng() % N + 1);
}