oj.uz

Submission #536971

# Submission time Handle Problem Language Result Execution time Memory
536971 2022-03-14T08:30:52 Z zaneyu Speedrun (RMI21_speedrun) C++14
71 / 100
 221 ms 924 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define unq(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const int maxn=2e3+5;
using namespace std;
vector<int> v[maxn];
void dfs(int u,int p){
	REP(j,10) setHint(u,j+1,(p&(1<<j))>>j);
	if(u>1){
		v[u].erase(find(ALL(v[u]),p));
	}
	if(sz(v[u])) REP(j,10) setHint(u,j+11,(v[u][0]&(1<<j))>>j);
	REP(j,sz(v[u])){
		int x=v[u][j];
		int nxt=u;
		if(j<sz(v[u])-1) nxt=v[u][j+1];
		REP(j,10) setHint(x,j+21,(nxt&(1<<j))>>j);
		dfs(x,u);
	}
}
void dfs3(int u,int p){
	REP(j,10) setHint(u,j+1,(p&(1<<j))>>j);
	if(u>1){
		v[u].erase(find(ALL(v[u]),p));
	}
	if(sz(v[u])) REP(j,10) setHint(u,j+11,(v[u][0]&(1<<j))>>j);
	else REP(j,10) setHint(u,j+11,0);
	REP(j,sz(v[u])){
		int x=v[u][j];
		dfs3(x,u);
	}
}
void assignHints(int subtask, int n, int A[], int B[]) {
	REP1(i,n-1){
		v[A[i]].pb(B[i]);
		v[B[i]].pb(A[i]);
	}
	if(subtask==2){
		setHintLen(20);
		REP1(i,n){
			if(sz(v[i])==n-1){
				REP1(a,n) REP(j,10) setHint(a,j+1,(i&(1<<j))>>j);
			}
		}
		return;
	}
	if(subtask==3){
		setHintLen(20);
		REP1(i,n){
			if(sz(v[i])==1){
				dfs(i,1023);
			}
		}
		return;
	}
	setHintLen(30);

	dfs(1,1023);
}
void gotoo(int x){
	if(x==0) assert(false);
	goTo(x);
}
void dfs2(int u){
	int p=0;
	REP(j,10) p=(p<<1)+getHint(10-j);
	int x=0;
	REP(j,10) x=(x<<1)+getHint(20-j);
	if(x==0){
		gotoo(p);
		return;
	}
	while(x!=u){
		gotoo(x);
		int nx=0;
		REP(j,10) nx=(nx<<1)+getHint(30-j);
		dfs2(x);
		x=nx;
	}
	if(u!=1) gotoo(p);
}
void dfs4(int u){
	int x=0;
	REP(j,10) x=(x<<1)+getHint(20-j);
	if(x==0){
		return;
	}
	dfs4(x);
}
void speedrun(int subtask, int n, int start) {
	if(subtask==2){
		int p=0;
		REP(j,10) p=(p<<1)+getHint(10-j);
		goTo(p);
		REP1(i,n){
			goTo(i);
			goTo(p);
		}
		return;
	}
	if(subtask==3){
		while(true){
			int p=0;
			REP(j,10) p=(p<<1)+getHint(10-j);
			if(p==1023) break;
			start=p;
		}
		dfs4(start);
		return;
	}
	while(start!=1){
		int p=0;
		REP(j,10) p=(p<<1)+getHint(10-j);
		gotoo(p);
		start=p;
	}
	dfs2(1);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 672 KB Output is correct
2 Correct 138 ms 860 KB Output is correct
3 Correct 221 ms 672 KB Output is correct
4 Correct 178 ms 752 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 720 KB Output is correct
2 Correct 95 ms 672 KB Output is correct

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 828 KB Output is correct
2 Correct 186 ms 672 KB Output is correct
3 Correct 148 ms 672 KB Output is correct
4 Correct 180 ms 760 KB Output is correct
5 Correct 207 ms 764 KB Output is correct
6 Correct 142 ms 684 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 194 ms 756 KB Partial solution
2 Partially correct 172 ms 684 KB Partial solution
3 Partially correct 158 ms 684 KB Partial solution
4 Partially correct 108 ms 924 KB Partial solution
5 Partially correct 143 ms 676 KB Partial solution
6 Partially correct 193 ms 796 KB Partial solution
7 Partially correct 128 ms 684 KB Partial solution