oj.uz

Submission #1116923

# Submission time Handle Problem Language Result Execution time Memory
1116923 2024-11-22T15:10:14 Z StefanSebez Speedrun (RMI21_speedrun) C++14
63 / 100
 598 ms 1172 KB 
#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1050;
vector<int>E[N],cvorovi;
int par[N];
void DFS(int u,int parent){
	cvorovi.pb(u);
	par[u]=parent;
	for(auto i:E[u]){
		if(i==parent) continue;
		DFS(i,u);
	}
}
void assignHints(int subtask, int n, int A[], int B[]) {
	for(int i=1;i<n;i++){E[A[i]].pb(B[i]),E[B[i]].pb(A[i]);}
	DFS(1,0);
	setHintLen(30);
	for(int i=1;i<=n;i++){
		for(int j=1,u=par[i];j<=10;j++,u>>=1){
			setHint(i,j,u&1);
		}
	}
	for(int I=0;I<n-1;I++){
		int i=cvorovi[I];
		int u=cvorovi[I+1],v=par[u];
		for(int j=11;j<=20;j++,v>>=1){
			setHint(i,j,v&1);
		}
		for(int j=21;j<=30;j++,u>>=1){
			setHint(i,j,u&1);
		}
	}
}

void speedrun(int subtask, int n, int start) {
	int U=start;
	while(U!=1){
		int v=0;for(int j=1;j<=10;j++) v+=getHint(j)*(1<<(j-1));
		goTo(v);
		U=v;
	}
	int par[n+10]={0},ct=n-1;
	while(ct--){
		int u=0;for(int j=11;j<=20;j++) u+=getHint(j)*(1<<(j-11));
		int v=0;for(int j=21;j<=30;j++) v+=getHint(j)*(1<<(j-21));
		while(U!=u){
			goTo(par[U]);
			U=par[U];
		}
		goTo(v);
		U=v;par[v]=u;
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 1172 KB Output is correct
2 Correct 576 ms 1100 KB Output is correct
3 Correct 559 ms 940 KB Output is correct
4 Correct 598 ms 848 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 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 2 ms 336 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 579 ms 848 KB Output is correct
2 Correct 556 ms 844 KB Output is correct
3 Correct 579 ms 852 KB Output is correct
4 Correct 536 ms 932 KB Output is correct
5 Correct 579 ms 924 KB Output is correct
6 Correct 549 ms 860 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 576 ms 924 KB Partial solution
2 Partially correct 561 ms 916 KB Partial solution
3 Partially correct 553 ms 860 KB Partial solution
4 Partially correct 570 ms 860 KB Partial solution
5 Partially correct 552 ms 860 KB Partial solution
6 Partially correct 572 ms 672 KB Partial solution
7 Partially correct 562 ms 1108 KB Partial solution