oj.uz

Submission #1040298

# Submission time Handle Problem Language Result Execution time Memory
1040298 2024-07-31T23:38:34 Z Edu175 Speedrun (RMI21_speedrun) C++17
100 / 100
 113 ms 1456 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,mxcont=b;i<mxcont;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto jfhg:v)cout<<jfhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

void sethint(ll i, ll j, ll b){
	setHint(i+1,j+1,b);
}
bool gethint(ll j){
	return getHint(j+1);
}
bool go(ll x){
	return goTo(x+1);
}
void assignHints(int subtask, int n, int U[], int V[]) { /* your solution here */
	vector<vector<ll>> g(n);
	fore(i,1,n){
		U[i]--,V[i]--;
		g[U[i]].pb(V[i]);
		g[V[i]].pb(U[i]);
	}
	/*fore(i,0,n){
		cout<<i<<": ";
		imp(g[i]);
	}*/
	vector<ll>ord,vis(n),fa(n);
	auto dfs=[&](ll x, auto &&dfs)->void{
		vis[x]=1; ord.pb(x);
		for(auto y:g[x])if(!vis[y]){
			fa[y]=x;
			dfs(y,dfs);
		}
	};
	dfs(0,dfs);
	// imp(ord);
	setHintLen(20);
	fore(i,0,n){
		ll x=ord[i],y=(i==n-1?1023:ord[i+1]);
		fore(j,0,10)sethint(x,j,fa[x]>>j&1);
		fore(j,0,10)sethint(x,j+10,y>>j&1);
	}
}

void speedrun(int subtask, int n, int s) { /* your solution here */
	s--;
	ll x=s;
	auto get=[&](ll b){
		ll mk=0;
		fore(i,0,10)mk|=ll(gethint(i+10*b))<<i;
		// cout<<"get "<<b<<": "<<mk<<"\n";
		return mk;
	}; 
	// cout<<x<<endl;
	auto up=[&](ll &x){
		x=get(0);
		// cout<<"up "<<x<<endl;
		assert(go(x));
	};
	while(x){
		up(x);
	}
	// raiz
	queue<ll>q;
	while(x<n){
		q.push(get(1));
		while(q.front()<n&&!go(q.front()))up(x);
		x=q.front(); q.pop();
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 684 KB Output is correct
2 Correct 109 ms 684 KB Output is correct
3 Correct 98 ms 1204 KB Output is correct
4 Correct 108 ms 944 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 856 KB Output is correct
2 Correct 89 ms 1100 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 688 KB Output is correct
2 Correct 99 ms 836 KB Output is correct
3 Correct 80 ms 836 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 684 KB Output is correct
2 Correct 106 ms 688 KB Output is correct
3 Correct 104 ms 684 KB Output is correct
4 Correct 102 ms 684 KB Output is correct
5 Correct 103 ms 1456 KB Output is correct
6 Correct 113 ms 828 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 684 KB Output is correct
2 Correct 112 ms 1192 KB Output is correct
3 Correct 98 ms 688 KB Output is correct
4 Correct 83 ms 1080 KB Output is correct
5 Correct 101 ms 700 KB Output is correct
6 Correct 84 ms 940 KB Output is correct
7 Correct 94 ms 700 KB Output is correct