Submission #1000414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000414		pcc	Speedrun (RMI21_speedrun)	C++17	100 / 100	170 ms	1592 KiB

speedrun

#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 (stderr)

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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40