oj.uz

Submission #536965

# Submission time Handle Problem Language Result Execution time Memory
536965 2022-03-14T08:20:41 Z jamezzz Speedrun (RMI21_speedrun) C++17
100 / 100
 119 ms 852 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define pb push_back

vector<int> AL[1005],pre;
int par[1005],nx[1005];

void dfs(int u,int p){
	par[u]=p;pre.pb(u);
	for(int v:AL[u]){
		if(v!=p)dfs(v,u);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	for(int i=1;i<N;++i)AL[A[i]].pb(B[i]),AL[B[i]].pb(A[i]);
	dfs(1,0);pre.pb(0);
	setHintLen(20);
	for(int i=1;i<=N;++i){
		for(int j=1;j<=10;++j)if(par[i]&(1<<(j-1)))setHint(i,j,1);
		for(int j=11;j<=20;++j)if(pre[i]&(1<<(j-11)))setHint(pre[i-1],j,1);
	}
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	int cur=start;
	memset(par,-1,sizeof par);
	memset(nx,-1,sizeof nx);
	while(cur!=1){
		if(par[cur]==-1){
			par[cur]=0,nx[cur]=0;
			for(int j=1;j<=10;++j)if(getHint(j))par[cur]+=1<<(j-1);
			for(int j=11;j<=20;++j)if(getHint(j))nx[cur]+=1<<(j-11);
		}
		goTo(par[cur]);cur=par[cur];
	}
	while(true){//Euler tour
		if(par[cur]==-1){
			par[cur]=0,nx[cur]=0;
			for(int j=1;j<=10;++j)if(getHint(j))par[cur]+=1<<(j-1);
			for(int j=11;j<=20;++j)if(getHint(j))nx[cur]+=1<<(j-11);
		}
		if(nx[cur]==0)break;
		int to=nx[cur];
		while(!goTo(to)){
			goTo(par[cur]);
			cur=par[cur];
		}
		cur=to;
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 768 KB Output is correct
2 Correct 94 ms 688 KB Output is correct
3 Correct 119 ms 672 KB Output is correct
4 Correct 98 ms 712 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 672 KB Output is correct
2 Correct 81 ms 684 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 740 KB Output is correct
2 Correct 91 ms 676 KB Output is correct
3 Correct 68 ms 712 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 832 KB Output is correct
2 Correct 94 ms 672 KB Output is correct
3 Correct 101 ms 732 KB Output is correct
4 Correct 94 ms 708 KB Output is correct
5 Correct 100 ms 672 KB Output is correct
6 Correct 74 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 852 KB Output is correct
2 Correct 104 ms 684 KB Output is correct
3 Correct 89 ms 836 KB Output is correct
4 Correct 101 ms 720 KB Output is correct
5 Correct 99 ms 724 KB Output is correct
6 Correct 94 ms 716 KB Output is correct
7 Correct 94 ms 716 KB Output is correct