#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define sz(a) (int)a.size()
#define all(v) v.begin(),v.end()
/*
void setHintLen(int l){}
void setHint(int i,int j,bool b){}
int getLength(){}
bool getHint(int j){}
bool goTo(int x){}
*/
void dfsHint(int u, int par, vector<vector<int>>& adj, vector<int>& right_neighbor, vector<int>& parent, vector<int>& left_child){
parent[u] = par;
vector<int> nodes;
for(int v: adj[u]){
if(v == par)continue;
dfsHint(v, u, adj, right_neighbor, parent, left_child);
nodes.pb(v);
}
if(sz(nodes))left_child[u] = nodes[0];
for(int i = 0;i + 1 < sz(nodes); ++i){
right_neighbor[nodes[i]] = nodes[i + 1];
}
}
void assignHints(int subtask, int N, int A[], int B[]) {
if(subtask == 1){
setHintLen(N);
for(int i = 1;i <= N - 1; ++i){
setHint(A[i], B[i], 1);
setHint(B[i], A[i], 1);
}
}else if(subtask == 3){
setHintLen(20);
vector<vector<int>> adj(N + 1);
for(int i = 1;i <= N - 1; ++i){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
for(int i = 1;i <= N; ++i){
if(sz(adj[i]) == 1)adj[i].pb(0);
int f = 0;
for(int v: adj[i])
{
for(int j = 9;j >= 0; --j){
if(v & (1 << j))setHint(i, f * 10 + j + 1, 1);
}
++f;
}
}
}else if(subtask == 2){
setHintLen(10);
vector<int> deg(N + 5, 0);
for(int i = 1;i <= N - 1; ++i){
deg[A[i]]++;
deg[B[i]]++;
}
int r = -1;
for(int i = 1;i <= N; ++i){
if(deg[i] == N - 1)r = i;
}
assert(r != -1);
for(int i = 1;i <= N; ++i){
for(int j = 10; j >= 1; --j){
if(r & (1 << (j - 1)))setHint(i, j, 1);
}
}
}else{
int n = N;
setHintLen(30);
vector<vector<int>> adj(n + 1);
for(int i = 1;i <= n - 1; ++i){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
vector<int> right_neighbor(n + 1, 0), parent(n + 1, 0), left_child(n + 1, 0);
dfsHint(1, 0, adj, right_neighbor, parent, left_child);
for(int i = 1;i <= n; ++i){
int idx = 1;
for(int j = 9;j >= 0; --j){
if(parent[i] & (1 << j))setHint(i, idx, 1);
++idx;
}
for(int j = 9;j >= 0; --j){
if(left_child[i] & (1 << j))setHint(i, idx, 1);
++idx;
}
for(int j = 9;j >= 0; --j){
if(right_neighbor[i] & (1 << j))setHint(i, idx, 1);
++idx;
}
}
}
}
void dfs1(int u, int par, vector<bool>& vis, int n){
vis[u] = true;
for(int v = 1;v <= n; ++v){
if(!vis[v] && getHint(v) == 1){
int x = goTo(v);
assert(x == 1);
dfs1(v, u, vis, n);
}
}
if(par != -1){
int x = goTo(par);
assert(x == 1);
}
}
void dfs3(int u, int par, vector<bool>& vis, vector<vector<int>>& adj){
vis[u] = true;
int A = 0, B = 0;
for(int j = 20;j >= 11; --j){
if(getHint(j) == 1){
A += (1 << (j - 10 - 1));
}
}
for(int j = 10; j >= 1; --j){
if(getHint(j) == 1){
B += (1 << (j - 1));
}
}
adj[u].pb(A);
adj[u].pb(B);
for(int v: adj[u]){
if(v == 0)continue;
if(!vis[v]){
int x = goTo(v);
assert(x == 1);
dfs3(v, u, vis, adj);
}
}
if(par != -1){
int x = goTo(par);
assert(x == 1);
}
}
void dfs4(int u, vector<bool>& vis){
int lc = 0, rn = 0, par = 0, idx = 1;
for(int j = 9;j >= 0; --j){
if(getHint(idx))par += (1 << j);
++idx;
}
for(int j = 9;j >= 0; --j){
if(getHint(idx))lc += (1 << j);
++idx;
}
for(int j = 9;j >= 0; --j){
if(getHint(idx))rn += (1 << j);
++idx;
}
vis[u] = true;
if(lc && !vis[lc]){
goTo(lc);
dfs4(lc, vis);
}
if(par != 0 && rn){
goTo(par);
goTo(rn);
dfs4(rn, vis);
}
if(par != 0){
goTo(par);
dfs4(par, vis);
}
}
void speedrun(int subtask, int N, int start) {
if(subtask == 1){
int l = getLength();
vector<bool> vis(N + 5, false);
dfs1(start, -1, vis, N);
}else if(subtask == 3){
int l = getLength();
vector<bool> vis(N + 5, false);
vector<vector<int>> adj(N + 5);
dfs3(start, -1, vis, adj);
}else if(subtask == 2){
int l = getLength();
int r = 0;
for(int j = 1;j <= 10; ++j){
if(getHint(j) == 1)r += (1 << (j - 1));
}
if(start != r)goTo(r);
for(int i = 1;i <= N; ++i){
if(r != i){
goTo(i);
goTo(r);
}
}
}else{
int l = getLength();
vector<bool> vis(N + 5, false);
dfs4(start, vis);
}
}
/*
int32_t main(){
}
*/
Compilation message
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:190:13: warning: unused variable 'l' [-Wunused-variable]
190 | int l = getLength();
| ^
speedrun.cpp:194:13: warning: unused variable 'l' [-Wunused-variable]
194 | int l = getLength();
| ^
speedrun.cpp:199:13: warning: unused variable 'l' [-Wunused-variable]
199 | int l = getLength();
| ^
speedrun.cpp:214:13: warning: unused variable 'l' [-Wunused-variable]
214 | int l = getLength();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
912 KB |
Output is correct |
| 2 |
Correct |
48 ms |
772 KB |
Output is correct |
| 3 |
Correct |
40 ms |
772 KB |
Output is correct |
| 4 |
Correct |
50 ms |
772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
720 KB |
Output is correct |
| 2 |
Correct |
50 ms |
704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
832 KB |
Output is correct |
| 2 |
Correct |
110 ms |
676 KB |
Output is correct |
| 3 |
Correct |
100 ms |
784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
660 KB |
Output is correct |
| 2 |
Correct |
76 ms |
820 KB |
Output is correct |
| 3 |
Correct |
115 ms |
660 KB |
Output is correct |
| 4 |
Correct |
115 ms |
704 KB |
Output is correct |
| 5 |
Correct |
96 ms |
672 KB |
Output is correct |
| 6 |
Correct |
138 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
82 ms |
752 KB |
Partial solution |
| 2 |
Partially correct |
72 ms |
672 KB |
Partial solution |
| 3 |
Partially correct |
108 ms |
732 KB |
Partial solution |
| 4 |
Partially correct |
115 ms |
660 KB |
Partial solution |
| 5 |
Partially correct |
105 ms |
660 KB |
Partial solution |
| 6 |
Partially correct |
90 ms |
800 KB |
Partial solution |
| 7 |
Partially correct |
132 ms |
780 KB |
Partial solution |
