oj.uz

Submission #500896

# Submission time Handle Problem Language Result Execution time Memory
500896 2022-01-01T15:30:56 Z mosiashvililuka Speedrun (RMI21_speedrun) C++14
100 / 100
 127 ms 976 KB 
#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,p[1009],pi,msh[1009];
vector <int> v[1009];
void dfs(int q, int w){
	pi++;p[pi]=q;msh[q]=w;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
	}
}
void assignHints(int subtask, int NN, int AA[], int BB[]) {
	setHintLen(20);
	a=NN;
	for(i=1; i<a; i++){
		v[AA[i]].push_back(BB[i]);
		v[BB[i]].push_back(AA[i]);
	}
	dfs(1,0);
	for(i=1; i<=a; i++){
		if(i<a){
		c=p[i+1];d=1;
		while(c>0){
			if(c%2==1) setHint(p[i],d,1);
			c/=2;d++;
		}
		}
		c=msh[p[i]];d=11;
		while(c>0){
			if(c%2==1) setHint(p[i],d,1);
			c/=2;d++;
		}
	}
}
int MSH(int q){
	int qw=0,we=1;
	for(int h=11; h<=20; h++){
		if(getHint(h)) qw+=we;
		we*=2;
	}
	return qw;
}
int nxt(int q){
	int qw=0,we=1;
	for(int h=1; h<=10; h++){
		if(getHint(h)) qw+=we;
		we*=2;
	}
	return qw;
}
void dfs(int q){
	int w=nxt(q);
	if(w==0) return;
	while(goTo(w)==0){
		int qw=MSH(q);
		goTo(qw);
		q=qw;
	}
	dfs(w);
}
void speedrun(int subtask, int NN, int start) {
	a=NN;c=start;
	while(c!=1){
		zx=MSH(c);
		goTo(zx);
		c=zx;
	}
	dfs(1);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 696 KB Output is correct
2 Correct 110 ms 660 KB Output is correct
3 Correct 120 ms 684 KB Output is correct
4 Correct 111 ms 676 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 700 KB Output is correct
2 Correct 124 ms 976 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 676 KB Output is correct
2 Correct 112 ms 712 KB Output is correct
3 Correct 79 ms 660 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 716 KB Output is correct
2 Correct 97 ms 704 KB Output is correct
3 Correct 122 ms 688 KB Output is correct
4 Correct 100 ms 676 KB Output is correct
5 Correct 122 ms 660 KB Output is correct
6 Correct 98 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 660 KB Output is correct
2 Correct 110 ms 804 KB Output is correct
3 Correct 83 ms 672 KB Output is correct
4 Correct 93 ms 656 KB Output is correct
5 Correct 122 ms 716 KB Output is correct
6 Correct 102 ms 692 KB Output is correct
7 Correct 127 ms 660 KB Output is correct