// 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);
auto isp = [&] (int u, int p) {
if (p == (1 << (MAXL / 2)) - 1) {
return 1;
}
if (p == 1) {
return 1;
}
if (vis[u] == (1 << (MAXL / 2)) - 1) {
return 0;
}
if (u == 1) {
return 0;
}
goTo(p);
int sib = get(1);
goTo(u);
if (sib <= n && goTo(sib)) {
assert(goTo(u));
return 0;
} else {
return 1;
}
};
auto dfs = [&] (auto &&self, int u, int p) {
if (0) {
return;
}
cerr << ' ' << u << ' ' << p << '\n';
if (u == (1 << (MAXL / 2)) - 1) {
return;
}
int chi = get(0), sib = get(1);
vis[u] = sib;
if (chi == 0) {
assert(p != -1);
assert(goTo(p));
return;
}
while (1) {
if (chi == p || (p == -1 && isp(u, chi))) {
break;
}
if (vis[chi]) {
chi = vis[chi];
continue;
}
cerr << " " << u << ' ' << chi << '\n';
assert(goTo(chi));
self(self, chi, u);
}
if (p == -1) {
p = chi;
if (p == (1 << (MAXL / 2)) - 1) {
return;
}
assert(goTo(p));
self(self, p, -1);
} else {
assert(goTo(p));
}
};
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
4
*/
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 |
Correct |
64 ms |
672 KB |
Output is correct |
| 2 |
Correct |
120 ms |
700 KB |
Output is correct |
| 3 |
Correct |
98 ms |
692 KB |
Output is correct |
| 4 |
Correct |
71 ms |
732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
672 KB |
Output is correct |
| 2 |
Correct |
52 ms |
708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
804 KB |
Output is correct |
| 2 |
Correct |
99 ms |
728 KB |
Output is correct |
| 3 |
Correct |
103 ms |
732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
672 KB |
Output is correct |
| 2 |
Correct |
82 ms |
672 KB |
Output is correct |
| 3 |
Correct |
57 ms |
700 KB |
Output is correct |
| 4 |
Correct |
70 ms |
676 KB |
Output is correct |
| 5 |
Correct |
85 ms |
688 KB |
Output is correct |
| 6 |
Correct |
44 ms |
696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
700 KB |
Output is correct |
| 2 |
Correct |
75 ms |
672 KB |
Output is correct |
| 3 |
Correct |
66 ms |
680 KB |
Output is correct |
| 4 |
Correct |
116 ms |
800 KB |
Output is correct |
| 5 |
Correct |
72 ms |
672 KB |
Output is correct |
| 6 |
Correct |
83 ms |
672 KB |
Output is correct |
| 7 |
Correct |
51 ms |
676 KB |
Output is correct |
