oj.uz

Submission #1095590

# Submission time Handle Problem Language Result Execution time Memory
1095590 2024-10-02T15:31:40 Z peti1234 Speedrun (RMI21_speedrun) C++17
100 / 100
 79 ms 1200 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 936 KB Output is correct
2 Correct 48 ms 684 KB Output is correct
3 Correct 73 ms 940 KB Output is correct
4 Correct 60 ms 940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 688 KB Output is correct
2 Correct 57 ms 1200 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 684 KB Output is correct
2 Correct 51 ms 720 KB Output is correct
3 Correct 51 ms 684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 684 KB Output is correct
2 Correct 79 ms 1200 KB Output is correct
3 Correct 53 ms 684 KB Output is correct
4 Correct 63 ms 940 KB Output is correct
5 Correct 49 ms 856 KB Output is correct
6 Correct 68 ms 940 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1112 KB Output is correct
2 Correct 47 ms 936 KB Output is correct
3 Correct 71 ms 1100 KB Output is correct
4 Correct 55 ms 708 KB Output is correct
5 Correct 66 ms 868 KB Output is correct
6 Correct 72 ms 932 KB Output is correct
7 Correct 59 ms 856 KB Output is correct