oj.uz

Submission #924060

# Submission time Handle Problem Language Result Execution time Memory
924060 2024-02-08T10:44:15 Z shoryu386 Speedrun (RMI21_speedrun) C++17
100 / 100
 1496 ms 4680 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;


bool vis[1007];
int parset[1007];
vector<int> adj[1007];
vector<int> dorder[1007];
int n;
void dfs(int x, int p, int d){
	vis[x] = 1;
	parset[x] = p;
	dorder[d].push_back(x);
	for (auto y : adj[x]){
		if (!vis[y]){
			dfs(y, x, d+1);
		}
	}
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	
	setHintLen(20);
	
	for (int x = 1; x < N; x++){
		adj[A[x]].push_back(B[x]);
		adj[B[x]].push_back(A[x]);
	}
	
	
	//let root be 1 always 
	dfs(1, 0, 0);
	
	vector<int> inorder;
	for (int x = 0; x <= N; x++){
		for (auto y : dorder[x]){
			inorder.push_back(y);
		}
	}
	
	//data 1 is par
	//data 2 is next
	
	int next[N+1];
	for (int x = 0; x < N-1; x++){
		next[ inorder[x] ] = inorder[x+1];
	}
	next[inorder[N-1]] = inorder[0];
	
	//encryption
	for (int x = 1; x <= N; x++){
		for (int z = 0; z <= 9; z++){
			if (parset[x] & (1<<z)){
				setHint(x, z+1, 1);
			}
		}
		
		for (int z = 0; z <= 9; z++){
			if (next[x] & (1<<z)){
				setHint(x, z+11, 1);
			}
		}
	}
	
	return;
}

int par[1007];
int nextt[1007];
int cur;

#define WEIRD -23145

int nn;
inline void setDetails(){
	if (nextt[cur] != WEIRD) return;
	
	par[cur] = 0; nextt[cur] = 0;
	
	for (int z = 0; z <= 9; z++){
		if (getHint(z+1)){
			par[cur] += (1<<z);
		}
	}
	for (int z = 0; z <= 9; z++){
		if (getHint(z+11)){
			nextt[cur] += (1<<z);
		}
	}
}

inline void assertGoTo(int x){
	goTo(x);
}

inline void returnToRoot(){
	setDetails();
	
	int steps = 0;
	while (cur != 1){
		assertGoTo(par[cur]);
		cur = par[cur];
		setDetails();
		
		assert(cur >= 1 && cur <= nn);
	}
}

vector<int> moves[1007];
inline void trace(int x){
	
	unordered_map<int, int> nodes;
	for (int y = 0; y < moves[x].size(); y++){
		nodes[moves[x][y]] = y+1;
	}
	nodes[1] = 0;
	
	while (nodes.count(cur) == 0){
		goTo(par[cur]);
		cur = par[cur];
	}
	
	int idx = nodes[cur];
	for (int z = idx; z < moves[x].size(); z++){
		goTo(moves[x][z]);
		cur = moves[x][z];
	}
	return;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	cur = start;
	nn = N;
	
	for (int x = 0; x < 1007; x++) par[x] = WEIRD;
	for (int x = 0; x < 1007; x++) nextt[x] = WEIRD;
	
	returnToRoot();
	vector<int> inorder;
	inorder.push_back(1);
	
	int ptr = 0;
	int nodeCount = 1;
	
	for (int z = 0; z < N-1; z++){
		int nextnode = nextt[inorder.back()];
		if (nextnode == 0) break;
		
		trace(inorder[ptr]);
		while (!goTo(nextnode)){
			ptr++;
			trace(inorder[ptr]);
		}
		
		nodeCount++;
		inorder.push_back(nextnode);
		
		cur = nextnode;
		
		moves[cur] = moves[inorder[ptr]];
		moves[cur].push_back(cur);
		
		setDetails();
	}
	
	
}

Compilation message

speedrun.cpp: In function 'void returnToRoot()':
speedrun.cpp:101:6: warning: unused variable 'steps' [-Wunused-variable]
  101 |  int steps = 0;
      |      ^~~~~
speedrun.cpp: In function 'void trace(int)':
speedrun.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int y = 0; y < moves[x].size(); y++){
      |                  ~~^~~~~~~~~~~~~~~~~
speedrun.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for (int z = idx; z < moves[x].size(); z++){
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1672 KB Output is correct
2 Correct 117 ms 4000 KB Output is correct
3 Correct 103 ms 2188 KB Output is correct
4 Correct 433 ms 3072 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1852 KB Output is correct
2 Correct 46 ms 1636 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 4680 KB Output is correct
2 Correct 1496 ms 3764 KB Output is correct
3 Correct 1198 ms 4208 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2312 KB Output is correct
2 Correct 75 ms 2704 KB Output is correct
3 Correct 56 ms 1644 KB Output is correct
4 Correct 375 ms 2868 KB Output is correct
5 Correct 106 ms 2140 KB Output is correct
6 Correct 60 ms 1676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2044 KB Output is correct
2 Correct 67 ms 1928 KB Output is correct
3 Correct 83 ms 1892 KB Output is correct
4 Correct 240 ms 3152 KB Output is correct
5 Correct 63 ms 1916 KB Output is correct
6 Correct 92 ms 2020 KB Output is correct
7 Correct 46 ms 1436 KB Output is correct