/*
// 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;
#else
#include "speedrun.h"
#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, curnode; 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);
}
Compilation message
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:145:6: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
145 | int cur = start;
| ^~~
speedrun.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
speedrun.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen(filein.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
speedrun.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(fileout.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
672 KB |
Output is correct |
| 2 |
Correct |
82 ms |
660 KB |
Output is correct |
| 3 |
Correct |
117 ms |
696 KB |
Output is correct |
| 4 |
Correct |
97 ms |
664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
696 KB |
Output is correct |
| 2 |
Correct |
82 ms |
660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
712 KB |
Output is correct |
| 2 |
Correct |
97 ms |
848 KB |
Output is correct |
| 3 |
Correct |
113 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
692 KB |
Output is correct |
| 2 |
Correct |
112 ms |
700 KB |
Output is correct |
| 3 |
Correct |
97 ms |
704 KB |
Output is correct |
| 4 |
Correct |
108 ms |
696 KB |
Output is correct |
| 5 |
Correct |
99 ms |
660 KB |
Output is correct |
| 6 |
Correct |
117 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
744 KB |
Output is correct |
| 2 |
Correct |
104 ms |
828 KB |
Output is correct |
| 3 |
Correct |
103 ms |
704 KB |
Output is correct |
| 4 |
Correct |
122 ms |
676 KB |
Output is correct |
| 5 |
Correct |
81 ms |
660 KB |
Output is correct |
| 6 |
Correct |
112 ms |
708 KB |
Output is correct |
| 7 |
Correct |
110 ms |
676 KB |
Output is correct |
