#include "speedrun.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
#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;
#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
//#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front
#define fr front
#define bc back
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '
//#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int maxn = 2e5 + 5;
int assign_par[maxn], assign_nxt[maxn];
vector<int> g[maxn];
int assign_last;
void dfs(int u, int p) {
assign_nxt[assign_last] = u; assign_last = u;
assign_par[u] = p;
for(int v: g[u]) {
if(v - p) {
dfs(v, u);
}
}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
int n = N;
fori(i,1,n - 1) {
g[A[i]].eb(B[i]);
g[B[i]].eb(A[i]);
}
dfs(1,0);
setHintLen(20);
fori(i,1,n) {
fori(bit, 0, 9) {
setHint(i, bit + 1, assign_par[i] >> bit & 1);
}
fori(bit, 0, 9) {
setHint(i, bit + 11, assign_nxt[i] >> bit & 1);
}
}
}
int speed_par[maxn];
int speed_nxt[maxn];
void prep_info(int now) {
if(!speed_par[now] and !speed_nxt[now]) {
fori(bit, 0, 9) {
int v = getHint(bit + 1);
speed_par[now] ^= (v << bit);
}
fori(bit, 0, 9) {
int v = getHint(bit + 11);
speed_nxt[now] ^= (v << bit);
}
// cout << now << ": " << speed_par[now] << speed_nxt[now] << endl;
}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
int n = N; int now = start;
prep_info(start);
while(now != 1) {
prep_info(now);
goTo(speed_par[now]); now = speed_par[now];
// cout << "now: " << now << endl;
}
fori(i,2,n) {
prep_info(now);
// cout << "now: " << now << sp << speed_par[now] << endl;
int nxt = speed_nxt[now];
// cout << now << " - > " << nxt << endl;
while(1) {
if(goTo(nxt)) {
now = nxt;
break;
}
else {
goTo(speed_par[now]);
now = speed_par[now];
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
10132 KB |
Output is correct |
| 2 |
Correct |
218 ms |
10132 KB |
Output is correct |
| 3 |
Correct |
142 ms |
10124 KB |
Output is correct |
| 4 |
Correct |
204 ms |
10188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
10112 KB |
Output is correct |
| 2 |
Correct |
239 ms |
10124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
10208 KB |
Output is correct |
| 2 |
Correct |
269 ms |
10076 KB |
Output is correct |
| 3 |
Correct |
202 ms |
10192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
10176 KB |
Output is correct |
| 2 |
Correct |
299 ms |
10132 KB |
Output is correct |
| 3 |
Correct |
208 ms |
10132 KB |
Output is correct |
| 4 |
Correct |
279 ms |
10124 KB |
Output is correct |
| 5 |
Correct |
233 ms |
10120 KB |
Output is correct |
| 6 |
Correct |
262 ms |
10184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
10204 KB |
Output is correct |
| 2 |
Correct |
143 ms |
10132 KB |
Output is correct |
| 3 |
Correct |
181 ms |
10204 KB |
Output is correct |
| 4 |
Correct |
265 ms |
10128 KB |
Output is correct |
| 5 |
Correct |
253 ms |
10260 KB |
Output is correct |
| 6 |
Correct |
269 ms |
10132 KB |
Output is correct |
| 7 |
Correct |
205 ms |
10232 KB |
Output is correct |
