Submission #1213079

#TimeUsernameProblemLanguageResultExecution timeMemory
1213079thelegendary08Stations (IOI20_stations)C++17
8 / 100
318 ms500 KiB
#include "stations.h" #include<bits/stdc++.h> #define pb push_back #define mp make_pair #define vi vector<int> #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i = k; i<n; i++) #define dout(x) cout<<x<<' '<<#x<<'\n'; #define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n'; #define vb vector<bool> using namespace std; const int mxn = 1005; vector<vi>adj(mxn); std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { f0r(i,n){ adj[i].clear(); } vi deg(n); f0r(i,n-1){ adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); deg[u[i]]++; deg[v[i]]++; } std::vector<int> labels(n); for (int i = 0; i < n; i++) { labels[i] = i + 1; } return labels; } int find_next_station(int s, int t, std::vector<int> c) { // cout<<s<<' '<<t<<'\n'; int os = s; int ot = t; int ds = 0; int dt = 0; f0r(i, 30){ if((1 << i) & s){ ds = i; } if((1<<i) & t){ dt = i; } } int lca; while(ds != dt){ if(dt > ds){ t = t/2; dt--; } else{ s = s/2; ds--; } } while(s != t){ s/=2; t/=2; } lca = s; // dout(lca); s = os; t = ot; vi path; path.pb(s); while(s != lca){ s/=2; path.pb(s); } vi p2; p2.pb(t); while(t != lca){ t /= 2; p2.pb(t); } p2.pop_back(); reverse(p2.begin(), p2.end()); for(auto u : p2){ path.pb(u); } // vout(path); f0r(i, path.size()){ if(path[i] == os)return path[i+1]; } return c[0]; }
#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...