oj.uz

Submission #925588

# Submission time Handle Problem Language Result Execution time Memory
925588 2024-02-12T05:43:34 Z penguin133 Speedrun (RMI21_speedrun) C++17
100 / 100
 71 ms 2892 KB 
#include <bits/stdc++.h>
using namespace std;
#include "speedrun.h"
int S[1005], back[1005], cnt = 1;
vector <int> adj[1005];
void dfs(int x, int par){
	S[x] = cnt++;
	for(int i = 0; i < 10; i++)if(par >> i & 1)setHint(x, i + 1, 1);
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	setHintLen(20);
	for(int i = 1; i <= N - 1; i++)adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
	dfs(1, 0);
	for(int i = 1; i <= N; i++)back[S[i]] = i;
	for(int i = 1; i <= N; i++){
		int x = back[S[i] + 1];
		for(int j = 0; j < 10; j++)if(x >> j & 1)setHint(i, j + 11, 1);
	}
}

int vis[1005];
void bruh(int x, int par, set <int> &pos){
	vis[x] = 1;
	int cnt = 0;
	for(int i = 11; i <= 20; i++)if(getHint(i))cnt += (1ll << (i - 11));
	
	int cnt2 = 0;
	for(int i = 1; i <= 10; i++)if(getHint(i))cnt2 += (1ll << (i - 1));

	set <int> cry;
	if(!vis[cnt]){
		bool ok = goTo(cnt);
		if(ok)bruh(cnt, x, pos);
		else pos.insert(cnt), cry.insert(cnt);
	}
	while(1){
		bool f = 0;
		for(auto i : pos){
			if(cry.find(i) != cry.end())continue;
			cry.insert(i);
			if(vis[i])continue;
			bool ok = goTo(i);
			if(ok){
				int tmp = i;
				pos.erase(i);
				bruh(tmp, x, pos);
				f = 1;
				break;
			}
		}
		if(!f)break;
	}
	if(!vis[cnt2]){
		bool ok = goTo(cnt2);
		if(ok)bruh(cnt2, x, pos);
	}
	if(par != -1)goTo(par);
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	set <int> br;
	vis[0] = vis[N + 1] = 1;
	bruh(start, -1, br);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1112 KB Output is correct
2 Correct 71 ms 2656 KB Output is correct
3 Correct 61 ms 1540 KB Output is correct
4 Correct 61 ms 1940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1616 KB Output is correct
2 Correct 56 ms 1644 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2164 KB Output is correct
2 Correct 48 ms 2148 KB Output is correct
3 Correct 52 ms 2892 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1876 KB Output is correct
2 Correct 57 ms 1364 KB Output is correct
3 Correct 59 ms 2140 KB Output is correct
4 Correct 48 ms 2396 KB Output is correct
5 Correct 63 ms 2032 KB Output is correct
6 Correct 65 ms 1372 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1360 KB Output is correct
2 Correct 59 ms 1620 KB Output is correct
3 Correct 59 ms 1628 KB Output is correct
4 Correct 48 ms 2324 KB Output is correct
5 Correct 69 ms 1372 KB Output is correct
6 Correct 64 ms 1620 KB Output is correct
7 Correct 56 ms 2404 KB Output is correct