Submission #504809

#	Time	Username	Problem	Language	Result	Execution time	Memory
504809		hohohaha	Speedrun (RMI21_speedrun)	C++14	100 / 100	299 ms	10260 KiB

speedrun

#include "speedrun.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
//#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

//#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int maxn = 2e5 + 5; 
int assign_par[maxn], assign_nxt[maxn]; 
vector<int> g[maxn]; 
int assign_last; 
void dfs(int u, int p) { 
	assign_nxt[assign_last] = u; assign_last = u; 
	assign_par[u] = p; 
	for(int v: g[u]) { 
	 	if(v - p) { 
	 		dfs(v, u); 
	 	}
	 }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	int n = N; 
	fori(i,1,n - 1) { 
		g[A[i]].eb(B[i]); 
		g[B[i]].eb(A[i]);
	}
	dfs(1,0); 
	setHintLen(20); 
	fori(i,1,n) { 
		fori(bit, 0, 9) { 
		 	setHint(i, bit + 1, assign_par[i] >> bit & 1); 
		 }
		 fori(bit, 0, 9) { 
		 	setHint(i, bit + 11, assign_nxt[i] >> bit & 1); 
		 }
	}
}

int speed_par[maxn]; 
int speed_nxt[maxn]; 
void prep_info(int now) { 
	if(!speed_par[now] and !speed_nxt[now]) { 
		fori(bit, 0, 9) { 
		 	int v = getHint(bit + 1); 
		 	speed_par[now] ^= (v << bit); 
		 }
		 fori(bit, 0, 9) { 
		 	int v = getHint(bit + 11); 
		 	speed_nxt[now] ^= (v << bit); 
		 }
//		 cout << now << ": " << speed_par[now] << speed_nxt[now] << endl; 
	}
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	int n = N; int now = start;
	prep_info(start);  
	while(now != 1) {
		prep_info(now); 
		goTo(speed_par[now]); now = speed_par[now]; 
//		 cout << "now: " << now << endl; 
	}
	fori(i,2,n) { 
		 prep_info(now); 
//		 cout << "now: " << now << sp << speed_par[now] << endl; 
		 int nxt = speed_nxt[now]; 
//		 cout << now << " - > " << nxt << endl; 
		 while(1) { 
		 	if(goTo(nxt))  { 
			 	now = nxt; 
			 	break; 
			 }
			 else { 
			  	goTo(speed_par[now]); 
				now = speed_par[now]; 
			}
		}
	}
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40