| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 538111 |
2022-03-16T05:39:26 Z |
kym |
Speedrun (RMI21_speedrun) |
C++14 |
|
132 ms |
1156 KB |
/* 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];
}
db2(cx,match[x]);
if(match[x] == -1) match[x] = 1;
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 */
memset(par,0,sizeof par);
int x = start;
while(x != 1) {
int prevx=x;
x=build1();
par[prevx]=x;
goTo(x);
if(x==1)break;
}
dba(par,1,N);
// im at the root now
set<int> s;
s.insert(1);
reach
for(;(int)s.size() < N;) {
db(x);
int b2 = build2();
assert(b2);
//assert(b2 >= 1);
//assert(b2 <= N);
bool r = goTo(b2);
if(r) {
par[b2] =x ;
dba(par,1,N);
x=b2;
s.insert(x);
continue;
} else {//
goTo(par[x]);
x=par[x];
while(goTo(b2) == 0) {
goTo(par[x]);
x = par[x];
}
par[b2]=x;
x=b2;
s.insert(x);
}
}
dba(par,1,N);
}
#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 time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
928 KB |
Output is correct |
| 2 |
Correct |
107 ms |
1092 KB |
Output is correct |
| 3 |
Correct |
116 ms |
1032 KB |
Output is correct |
| 4 |
Correct |
102 ms |
1040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
964 KB |
Output is correct |
| 2 |
Correct |
83 ms |
904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
1156 KB |
Output is correct |
| 2 |
Correct |
101 ms |
1064 KB |
Output is correct |
| 3 |
Correct |
62 ms |
1048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
94 ms |
932 KB |
Output is correct |
| 3 |
Correct |
132 ms |
976 KB |
Output is correct |
| 4 |
Correct |
77 ms |
1052 KB |
Output is correct |
| 5 |
Correct |
123 ms |
940 KB |
Output is correct |
| 6 |
Correct |
74 ms |
1020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
105 ms |
928 KB |
Output is correct |
| 3 |
Correct |
92 ms |
1048 KB |
Output is correct |
| 4 |
Correct |
95 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
106 ms |
1036 KB |
Output is correct |
| 6 |
Correct |
83 ms |
1012 KB |
Output is correct |
| 7 |
Correct |
80 ms |
928 KB |
Output is correct |
