/* Input format:
*
* N -- number of nodes
* a1 b1 -- edge 1
* ...
* a(N-1) b(N-1) -- edge N - 1
* x -- start node
*/
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
/*static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;
void setHintLen(int l) {
if (length_set) {
cerr << "Cannot call setHintLen twice" << endl;
exit(0);
}
length = l;
length_set = true;
}
void setHint(int i, int j, bool b) {
if (!length_set) {
cerr << "Must call setHintLen before setHint" << endl;
exit(0);
}
mp[i][j] = b;
}
int getLength() { return length; }
bool getHint(int j) { return mp[current_node][j]; }
bool goTo(int x) {
if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
++queries;
return false;
} else {
viz.insert(current_node = x);
return true;
}
}*/
void codifica(int poz,int a,int b)
{
for(int i=10;i>=1;--i)
{
setHint(poz,i,a%2);
a/=2;
}
for(int i=20;i>=11;--i)
{
setHint(poz,i,b%2);
b/=2;
}
}
void construieste(int nod,int uc,vector<int>a[],int t[])
{
if(nod==1)
{
codifica(nod,0,a[nod][0]);
int ant=0,ac=0;
for(auto x:a[nod])
{
if(ac==0)
ac=x;
else
{
ant=ac;
ac=x;
construieste(ant,ac,a,t);
}
t[x]=nod;
}
construieste(ac,0,a,t);
return;
}
if(a[nod].size()==1)
codifica(nod,t[nod],uc);
else
{
int ant=0,ac=0;
if(a[nod][0]!=t[nod])
codifica(nod,t[nod],a[nod][0]);
else
codifica(nod,t[nod],a[nod][1]);
for(auto x:a[nod])
{
if(t[nod]==x)
continue;
t[x]=nod;
if(ac==0)
ac=x;
else
{
ant=ac;
ac=x;
construieste(ant,ac,a,t);
}
}
construieste(ac,uc,a,t);
}
}
void assignHints(int subtask, int N, int A[], int B[])
{
setHintLen(20);
int n=N,t[1010];
vector<int>a[n+5];
t[n]=0;
for(int i=1;i<n;++i)
{
t[i]=0;
a[A[i]].push_back(B[i]);
a[B[i]].push_back(A[i]);
}
construieste(1,0,a,t);
}
int decodifica1()
{
int val=0;
for(int i=1;i<=10;++i)
{
val*=2;
val+=getHint(i);
}
return val;
}
int decodifica2()
{
int val=0;
for(int i=11;i<=20;++i)
{
val*=2;
val+=getHint(i);
}
return val;
}
void rezolva()
{
int nod=1,du=0;
stack<int>s;
s.push(1);
while(1)
{
while(goTo(nod=decodifica2()))
s.push(nod);
du=decodifica2();
if(du==0)
break;
s.pop();
goTo(s.top());
while(goTo(du)==false)
{
s.pop();
goTo(s.top());
}
nod=du;
s.push(nod);
du=0;
}
}
void speedrun(int subtask, int N, int start)
{
while(start!=1)
goTo(decodifica1());
exit(1);
rezolva();
}
/*int main() {
int N;
cin >> N;
int a[N], b[N];
for (int i = 1; i < N; ++i) {
cin >> a[i] >> b[i];
neighbours[a[i]].insert(b[i]);
neighbours[b[i]].insert(a[i]);
}
assignHints(1, N, a, b);
if (!length_set) {
cerr << "Must call setHintLen at least once" << endl;
exit(0);
}
cin >> current_node;
viz.insert(current_node);
speedrun(1, N, current_node);
if (viz.size() < N) {
cerr << "Haven't seen all nodes" << endl;
exit(0);
}
cerr << "OK; " << queries << " incorrect goto's" << endl;
return 0;
}*/
Compilation message
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:174:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
174 | while(start!=1)
| ^~~~~
speedrun.cpp:176:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
176 | exit(1);
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
82 ms |
816 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
103 ms |
828 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
1084 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
78 ms |
1004 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
1080 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
