oj.uz

Submission #1000414

# Submission time Handle Problem Language Result Execution time Memory
1000414 2024-06-17T13:11:08 Z pcc Speedrun (RMI21_speedrun) C++17
100 / 100
 170 ms 1592 KB 
#include "speedrun.h"

#include <bits/stdc++.h>
using namespace std;
const int mxn = 1010;

vector<int> tree[mxn];

vector<int> v;

void addint(int node,int head,int val){
	cerr<<"set:"<<node<<','<<head<<":"<<val<<endl;
	for(int i = 0;i<10;i++){
		if(val&(1<<i))setHint(node,head+i,1);
		else setHint(node,head+i,0);
	}
	return;
}

void dfs(int now,int par){
	cerr<<now<<','<<par<<endl;
	v.push_back(now);
	addint(now,1,par);
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		dfs(nxt,now);
	}
	return;
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	cerr<<"assigning"<<endl;
	setHintLen(20);
	for(int i = 1;i<N;i++){
		tree[A[i]].push_back(B[i]);
		tree[B[i]].push_back(A[i]);
	}
	dfs(1,1);
	v.push_back(v.back());
	for(int i = 0;i+1<v.size();i++){
		addint(v[i],11,v[i+1]);
	}
	return;
}

int par[mxn];

int getint(int node,int head){
	int re = 0;
	for(int i = 0;i<10;i++){
		if(getHint(head+i))re |= 1<<i;
	}
	return re;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	int now = start;
	while(now != 1){
		int up = getint(now,1);
		assert(goTo(up));
		now = up;
	}
	par[1] = 1;
	while(getint(now,11) != now){
		int nxt = getint(now,11);
		cerr<<now<<' '<<nxt<<endl;
		while(!goTo(nxt)){
			cerr<<now<<" failed, going to "<<par[now]<<endl;
			goTo(par[now]);
			now = par[now];
		}
		par[nxt] = now;
		now = nxt;
	}
	return;
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 932 KB Output is correct
2 Correct 144 ms 1160 KB Output is correct
3 Correct 169 ms 1168 KB Output is correct
4 Correct 152 ms 936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 1364 KB Output is correct
2 Correct 154 ms 1304 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1440 KB Output is correct
2 Correct 136 ms 1144 KB Output is correct
3 Correct 136 ms 1188 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1224 KB Output is correct
2 Correct 166 ms 684 KB Output is correct
3 Correct 141 ms 1452 KB Output is correct
4 Correct 150 ms 1436 KB Output is correct
5 Correct 150 ms 1404 KB Output is correct
6 Correct 170 ms 904 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1104 KB Output is correct
2 Correct 137 ms 1592 KB Output is correct
3 Correct 161 ms 1156 KB Output is correct
4 Correct 142 ms 1304 KB Output is correct
5 Correct 147 ms 1160 KB Output is correct
6 Correct 162 ms 1324 KB Output is correct
7 Correct 154 ms 1152 KB Output is correct