oj.uz

Submission #1066876

# Submission time Handle Problem Language Result Execution time Memory
1066876 2024-08-20T08:24:18 Z 김은성(#11121) Speedrun (RMI21_speedrun) C++17
63 / 100
 94 ms 1424 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> child[1009];
vector<int> graph[1009];
int par[1009];
void settree(int v){
	for(int u: graph[v]){
		if(par[v] == u)
			continue;
		par[u] = v;
		child[v].push_back(u);
		settree(u);
	}
}
int leftchild(){
	int ans = 0;
	for(int i=0; i<10; i++){
		if(getHint(i+1))
			ans |= (1<<i);
	}
	return ans;
}
int rightsibling(){
	int ans = 0;
	for(int i=0; i<10; i++){
		if(getHint(i+11))
			ans |= (1<<i);
	}
	return ans;
}
int parent(){
	int ans = 0;
	for(int i=0; i<10; i++){
		if(getHint(i+21))
			ans |= (1<<i);
	}
	return ans;
}
void setnumber(int v, int offset, int mask){
	for(int i=0; i<10; i++){
		if(mask & (1<<i))
			setHint(v, i+offset, 1);
	}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	setHintLen(30);
	int i;
	for(i=1; i<N; i++){
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	settree(1);
	for(i=1; i<=N; i++){
		setnumber(i, 1, child[i].empty() ? 0 : child[i][0]);
		int rs = 0;
		if(par[i]){
			int idx = find(child[par[i]].begin(), child[par[i]].end(), i) - child[par[i]].begin();
			if(idx+1 < child[par[i]].size())
				rs = child[par[i]][idx+1];
		}
		setnumber(i, 11, rs);
		setnumber(i, 21, par[i]);
	}
}
int n;
bool ch[1009];
void dfs(int v){
	int i;
	int p = parent(), l = leftchild(), r = rightsibling();
	//printf("v=%d l=%d r=%d\n", v,l, r);
	if(l){
		goTo(l);
		dfs(l);
		goTo(v);
	}
	if(r){
		goTo(p);
		goTo(r);
		dfs(r);
		goTo(v);
	}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
	n = N;
	dfs(start);
	while(parent()){
		start = parent();
		goTo(start);
	}
	dfs(1);
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if(idx+1 < child[par[i]].size())
      |       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
speedrun.cpp: In function 'void dfs(int)':
speedrun.cpp:69:6: warning: unused variable 'i' [-Wunused-variable]
   69 |  int i;
      |      ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 744 KB Output is correct
2 Correct 58 ms 1200 KB Output is correct
3 Correct 90 ms 936 KB Output is correct
4 Correct 81 ms 1200 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 684 KB Output is correct
2 Correct 64 ms 936 KB Output is correct
3 Correct 50 ms 684 KB Output is correct
4 Correct 87 ms 1424 KB Output is correct
5 Correct 68 ms 940 KB Output is correct
6 Correct 94 ms 940 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 49 ms 684 KB Partial solution
2 Partially correct 67 ms 684 KB Partial solution
3 Partially correct 62 ms 932 KB Partial solution
4 Partially correct 73 ms 1200 KB Partial solution
5 Partially correct 55 ms 684 KB Partial solution
6 Partially correct 55 ms 688 KB Partial solution
7 Partially correct 61 ms 940 KB Partial solution