Submission #1197571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197571		KK_1729	Speedrun (RMI21_speedrun)	C++20	100 / 100	57 ms	488 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
		vector<vector<int>> adj(N+1);
		FOR(i,1,N){
			adj[A[i]].pb(B[i]);
			adj[B[i]].pb(A[i]);
		}

		vector<int> arr;
		vector<int> visited(N+1);
		stack<int> s;
		s.push(1);
		vector<int> par(N+1);
		while (!s.empty()){
			int current = s.top();
			s.pop();

			if (visited[current]) continue;
			arr.pb(current);
			for (auto x: adj[current]){
				s.push(x);
				if (!visited[x]) par[x] = current;
			}
			visited[current] = 1;
		}
		setHintLen(20);
		// arr.pb(0);
		FOR(i,0,N){
			// int k = 0;
			int d = arr[(i+1)%N];
			FOR(j,0,10){
				if (par[arr[i]] & (1 << j)){
					// k |= (1 << j);
					setHint(arr[i], j+1, 1);
				}else{
					setHint(arr[i], j+1, 0);
				}
				if (d & (1 << j)){
					// k |= (1 << (j+10));
					setHint(arr[i], j+11, 1);
					
				}else{
					setHint(arr[i], j+11, 0);
				}
			}

			
		}
		// for (int x: arr) cout << x << " ";
		// cout << endl;
		return;

}

void speedrun(int subtask, int N, int start) { /* your solution here */
	vector<int> visited(N+1);
	int c = 0;
	int u = 0;
	while (start != 1){
		// u++;
		// if (u > 5) break;
		int par = 0;
		
		FOR(i,1,11){
			if (getHint(i)) par |= (1 << (i-1));
		}
		goTo(par);
		// cout << start << par << endl;
		start = par;
	}
	int current = start;
	int curtogo = 0;
	int o = 0;

	while (c < N){
		o++;
		// if (o > 40) break;
		int ne = 0;
		int par = 0;
		
		FOR(i,1,11){
			if (getHint(i)) par |= (1 << (i-1));
		}
		FOR(i,11,21){
			if (getHint(i)) ne |= (1 << (i-1-10));
		}
		if (!visited[current]){
			c++;
			visited[current] = 1;
		}
		// cout << current << curtogo << endl;
		if (curtogo){
			// visited[current] = 1;
			bool can = goTo(curtogo);
			if (can){
				current = curtogo;
				curtogo = 0;
			}else{
				goTo(par);
				current = par;
			}
		}else{
			if (!visited[ne]){
				bool can = goTo(ne);
				if (can){
					current = ne;
					curtogo = 0;
				}else{
					goTo(par);
					curtogo = ne;
				}
			}else{
				goTo(par);
				current = par;
				curtogo = 0;
			}
		}
	}
}

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