// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
#define MAXL 20
void assignHints(int subtask, int n, int a[], int b[]) {
vector<vi> adj(n + 5);
REP (i, 1, n) {
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
vi sib(n + 5, -1), chi(n + 5, -1);
auto dfs = [&] (auto &&self, int u, int p) {
if (0) {
return;
}
REP (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v == p) {
swap(adj[u][i], adj[u][adj[u].size() - 1]);
adj[u].pop_back();
break;
}
}
if (!adj[u].empty()) {
chi[u] = adj[u][0];
} else {
chi[u] = 0;
}
REP (i, 0, adj[u].size()) {
int v = adj[u][i];
if (i + 1 < adj[u].size()) {
sib[v] = adj[u][i + 1];
} else {
sib[v] = p;
}
self(self, v, u);
}
return;
};
sib[1] = 0;
dfs(dfs, 1, (1 << (MAXL / 2)) - 1);
setHintLen(MAXL);
REP (i, 1, n + 1) {
cerr << i << ": " << chi[i] << ' ' << sib[i] << '\n';
assert(chi[i] != -1);
REP (j, 0, MAXL / 2) {
if (chi[i] >> j & 1) {
setHint(i, j + 1, 1);
}
}
}
REP (i, 1, n + 1) {
assert(sib[i] != -1);
REP (j, 0, MAXL / 2) {
if (sib[i] >> j & 1) {
setHint(i, j + 1 + MAXL / 2, 1);
}
}
}
}
void speedrun(int subtask, int n, int start) {
auto get = [&] (bool sib) {
int res = 0;
REP (i, 0, MAXL / 2) {
res |= getHint(i + 1 + sib * MAXL / 2) << i;
}
return res;
};
vi vis(n + 5, 0);
bool done = 0;
auto dfs = [&] (auto &&self, int u, int p) {
if (0) {
return 0;
}
cerr << ' ' << u << ' ' << p << '\n';
if (u == (1 << (MAXL / 2)) - 1) {
done = 1;
return 0;
}
if (get(0) == 0) {
int sib = get(1);
vis[u] = sib;
assert(goTo(p));
cerr << sib << '\n';
return sib;
}
int sib = get(1);
int chi = get(0);
vis[u] = sib;
while (1) {
if (vis[chi]) {
if (vis[chi] == (1 << (MAXL / 2)) - 1) {
done = 1;
return 0;
}
if (goTo(vis[chi])) {
goTo(u);
chi = vis[chi];
continue;
}
}
cerr << " " << u << ' ' << chi << '\n';
assert(goTo(chi));
chi = self(self, chi, u);
if (done) {
break;
}
}
return sib;
};
int tmp = get(0);
if (tmp == 0) {
REP (i, 1, n + 1) {
if (i == start) continue;
if (goTo(i)) {
start = i;
break;
}
}
}
dfs(dfs, start, -1);
return;
}
/*
6
3 1
6 5
2 4
1 4
2 6
1
*/
Compilation message
speedrun.cpp: In instantiation of 'assignHints(int, int, int*, int*)::<lambda(auto:23&&, int, int)> [with auto:23 = assignHints(int, int, int*, int*)::<lambda(auto:23&&, int, int)>&]':
speedrun.cpp:75:38: required from here
speedrun.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
50 | REP (i, 0, adj[u].size()) {
| ~~~~~~~~~~~~~~~~~~~
speedrun.cpp:50:9: note: in expansion of macro 'REP'
50 | REP (i, 0, adj[u].size()) {
| ^~~
speedrun.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
63 | REP (i, 0, adj[u].size()) {
| ~~~~~~~~~~~~~~~~~~~
speedrun.cpp:63:9: note: in expansion of macro 'REP'
63 | REP (i, 0, adj[u].size()) {
| ^~~
speedrun.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (i + 1 < adj[u].size()) {
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
672 KB |
Solution didn't visit every node |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
672 KB |
Output is correct |
| 2 |
Correct |
72 ms |
672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
792 KB |
Output is correct |
| 2 |
Correct |
141 ms |
824 KB |
Output is correct |
| 3 |
Correct |
114 ms |
736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
744 KB |
Output is correct |
| 2 |
Correct |
61 ms |
752 KB |
Output is correct |
| 3 |
Correct |
63 ms |
676 KB |
Output is correct |
| 4 |
Correct |
92 ms |
720 KB |
Output is correct |
| 5 |
Correct |
109 ms |
860 KB |
Output is correct |
| 6 |
Correct |
51 ms |
692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
748 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
