Submission #1095590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095590		peti1234	Speedrun (RMI21_speedrun)	C++17	100 / 100	79 ms	1200 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

const int c=1005;
int n, fel[c];
vector<int> sz[c], sor;
bool v[c];

void dfs(int a) {
	v[a]=true;
	sor.push_back(a);
	//cout << "dfs " << a << "\n";
	for (auto x:sz[a]) {
		if (!v[x]) {
			fel[x]=a;
			dfs(x);
		}
	}
}
/*
bool fix[c][22], el[c][c];
void setHintLen(int a) {

}
void setHint(int a, int b, int c) {
	fix[a][b]=c;
}
int cur;
bool goTo(int a) {
	cout << "proba " << cur << " " << a << "\n";
	if (el[cur][a]) {
		cur=a;
		return true;
	}
	return false;
}
bool getHint(int a) {
	return fix[cur][a];
}
*/

void assignHints(int st, int N, int A[], int B[]) {
	n=N;
	for (int i=1; i<n; i++) {
		int x=A[i], y=B[i];
		sz[x].push_back(y), sz[y].push_back(x);
	}


	dfs(1);


	 setHintLen(20);
	 for (int i=1; i<=n; i++) {
		 for (int j=0; j<10; j++) {
			 if (fel[i] & (1<<j)) {
				 setHint(i, j+1, 1);
			 }
		 }
	 }
	 for (int i=0; i<n-1; i++) {
		 int a=sor[i], b=sor[i+1];
		 //cout << "par " << a << " " << b << "\n";
		 for (int j=0; j<10; j++) {
			 if (b & (1<<j)) {
				 setHint(a, j+11, 1);
			 }
		 }
	 }

}

int felett() {
	int res=0;
	for (int i=0; i<10; i++) {
		if (getHint(i+1)) {
			res+=(1<<i);
		}
	}
	return res;
}
int kov() {
	int res=0;
	for (int i=0; i<10; i++) {
		if (getHint(i+11)) {
			res+=(1<<i);
		}
	}
	return res;
}

bool lep(int a) {
	return goTo(a);
}

void speedrun(int st, int N, int pos) {
	n=N;
	while (pos!=1) {
		int s=felett();
		lep(s);
		pos=s;
	}

	int cel=kov();



	for (int i=1; i<n; i++) {
		while (!lep(cel)) {
			int f=felett();
			lep(f);
			pos=f;
		}
		pos=cel;
		cel=kov();
	}

	return;
}

/*
int main() {
	int st=1, n;
	cin >> n;
	int a[n-1], b[n-1];
	for (int i=0; i<n-1; i++) {
		cin >> a[i] >> b[i];
		el[a[i]][b[i]]=el[b[i]][a[i]]=1;
	}
	assignHints(st, n, a, b);
	cin >> cur;
	speedrun(st, n, cur);
}
*/
/*
10
1 2 1 3
2 4 2 5
3 6 3 7
7 8 7 9 7 10
4
*/

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