Submission #538077

#TimeUsernameProblemLanguageResultExecution timeMemory
538077kymSpeedrun (RMI21_speedrun)C++14
0 / 100
96 ms1032 KiB
/* 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> using namespace std; #define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i) #define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #define reach #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <ll, ll> pi; typedef tuple<ll,ll,ll> ti3; typedef tuple<ll,ll,ll,ll> ti4; ll rand(ll a, ll b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (ll)1e18 + 500; template <typename T> void chmax(T& a, const T b) { a=max(a,b); } template <typename T> void chmin(T& a, const T b) { a=min(a,b); } const int MAXN = -1; #include "speedrun.h" #ifdef LOCAL void setHintLen(int l); void setHint(int i, int j, bool b); int getLength() ; bool getHint(int j); bool goTo(int x); #endif vector<int> V[1005]; set<int> lft[1005]; int par[1005]; int match[1005]; void dfs(int x, int p ) { par[x] = p; for(auto v:V[x]) { if(v==p)continue; dfs(v,x); } } void gethints(int x, int p) { FOR(bit,0,9)if((1<<bit)&p)setHint(x,bit+1,1); if(p != 0)lft[x].erase(p); if(lft[x].size()) { //dbv(lft[x]); vector<int> children; for(auto i:lft[x])children.pb(i); // now the children will get each other FOR(i,0,children.size()-1) { // the last child contain the leaf that carries that information for the parent if(i != (int)children.size()-1 )match[children[i]] = children[i+1]; gethints(children[i],x); } FOR(bit,0,9)if((1<<bit)&children[0])setHint(x,10+bit+1,1); } else { int cx = x; while(match[x] == -1 && x != 0) { x=par[x]; } if(match[x] != -1) { FOR(bit,0,9)if((1<<bit)&match[x])setHint(cx,10+bit+1,1); } } } void assignHints(int subtask, int n, int A[], int B[]) { /* your solution here */ memset(match,-1,sizeof match); FOR(i,1,n-1) { V[A[i]].pb(B[i]); V[B[i]].pb(A[i]); lft[A[i]].insert(B[i]); lft[B[i]].insert(A[i]); } dfs(1,0); setHintLen(20); gethints(1,0); } int build1() { int r = 0; FOR(i,0,9){ bool st = getHint(i+1); if(st) r += 1<<i; } return r; } int build2() { int r = 0; FOR(i,0,9){ bool st = getHint(i+11); if(st) r += 1<<i; } return r; } void speedrun(int subtask, int N, int start) { /* your solution here */ int x = start; while(x != 1) { int x=build1(); goTo(x); if(x==1)break; } // im at the root now set<int> s; s.insert(1); reach for(;(int)s.size() < N;) { db(x); int b2 = build2(); //assert(b2 >= 1); //assert(b2 <= N); bool r = goTo(b2); if(r) { x=b2; s.insert(x); continue; } else {//root if(par[x] == 0)return; goTo(par[x]); x=par[x]; while(goTo(b2) == 0) { if(par[x] == 0)return; goTo(par[x]); x = par[x]; } x=b2; s.insert(x); } } } #ifdef LOCAL 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) { db2("GOTO: ", x); if (neighbours[current_node].find(x) == end(neighbours[current_node])) { ++queries; return false; } else { viz.insert(current_node = x); return true; } } 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); reach 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 ((int)viz.size() < N) { cerr << "Haven't seen all nodes" << endl; exit(0); } cerr << "OK; " << queries << " incorrect goto's" << endl; return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...