oj.uz

Submission #1116942

# Submission time Handle Problem Language Result Execution time Memory
1116942 2024-11-22T15:57:20 Z StefanSebez Speedrun (RMI21_speedrun) C++14
100 / 100
 431 ms 1364 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 DFS1(int u,int parent){
	for(int i=0;i<E[u].size();i++){
		if(E[u][i]==parent) swap(E[u][i],E[u].back());
	}
	for(auto i:E[u]) if(i!=parent) DFS1(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]);}
	if(subtask==2){
		int root=1;
		for(int i=1;i<=n;i++) if(E[i].size()>1) root=i;
		setHintLen(20);
		for(int i=1;i<=n;i++){
			if(i==root){
				setHint(i,1,1);
				continue;
			}
			for(int j=2,x=root;j<=11;j++,x>>=1) setHint(i,j,x&1);
		}
	}
	else if(subtask==3){
		int root=1;
		for(int i=1;i<=n;i++) if(E[i].size()==1) {root=i;}
		//printf("%i\n",root);
		DFS1(root,0);
		//for(int i=1;i<=n;i++) {printf("%i: ",i);for(auto j:E[i]) printf("%i ",j);printf("\n");}
		setHintLen(20);
		for(int i=1;i<=n;i++){
			int ct=1;
			for(auto u:E[i]){
				for(int x=u,cnt=1;cnt<=10;cnt++,ct++,x>>=1){
					setHint(i,ct,x&1);
				}
			}
		}
	}
	else{
		DFS(1,0);
		setHintLen(20);
		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++,u>>=1){
				setHint(i,j,u&1);
			}
			/*for(int j=21;j<=30;j++,u>>=1){
				setHint(i,j,u&1);
			}*/
		}
	}
}

void speedrun(int subtask, int n, int start) {
	if(subtask==2){
		int U=start;
		if(getHint(1)==0){
			int u=0;for(int j=2;j<=11;j++) u+=getHint(j)*(1<<(j-2));
			goTo(u);
			U=u;
		}
		for(int i=1;i<=n;i++){
			if(i==U) continue;
			goTo(i);
			goTo(U);
		}
	}
	else if(subtask==3){
		int U=start;
		while(1){
			int u=0;for(int j=1;j<=10;j++) u+=getHint(j)*(1<<(j-1));
			int v=0;for(int j=11;j<=20;j++) v+=getHint(j)*(1<<(j-11));
			//printf("%i: %i %i\n",U,u,v);
			goTo(u);
			U=u;
			if(u==0||v==0) break;
		}
		while(1){
			int u=0;for(int j=1;j<=10;j++) u+=getHint(j)*(1<<(j-1));
			int v=0;for(int j=11;j<=20;j++) v+=getHint(j)*(1<<(j-11));
			//printf("%i: %i %i\n",U,u,v);
			if(u==0||v==0) break;
			goTo(v);
			U=v;
		}
	}
	else{
		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(1){
				bool bul=goTo(u);
				if(bul==true){
					par[u]=U;
					U=u;
					break;
				}
				goTo(par[U]);
				U=par[U];
			}
			//goTo(v);
			//U=v;par[v]=u;
		}
	}
}

Compilation message

speedrun.cpp: In function 'void DFS1(int, int)':
speedrun.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<E[u].size();i++){
      |              ~^~~~~~~~~~~~
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:66:23: warning: unused variable 'v' [-Wunused-variable]
   66 |    int u=cvorovi[I+1],v=par[u];
      |                       ^
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:92:7: warning: variable 'U' set but not used [-Wunused-but-set-variable]
   92 |   int U=start;
      |       ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 916 KB Output is correct
2 Correct 397 ms 916 KB Output is correct
3 Correct 429 ms 852 KB Output is correct
4 Correct 417 ms 852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 668 KB Output is correct
2 Correct 206 ms 928 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 928 KB Output is correct
2 Correct 373 ms 1116 KB Output is correct
3 Correct 383 ms 924 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 1172 KB Output is correct
2 Correct 411 ms 1100 KB Output is correct
3 Correct 411 ms 1108 KB Output is correct
4 Correct 397 ms 1364 KB Output is correct
5 Correct 431 ms 864 KB Output is correct
6 Correct 426 ms 924 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1100 KB Output is correct
2 Correct 393 ms 1112 KB Output is correct
3 Correct 406 ms 952 KB Output is correct
4 Correct 426 ms 924 KB Output is correct
5 Correct 391 ms 924 KB Output is correct
6 Correct 399 ms 1124 KB Output is correct
7 Correct 403 ms 1176 KB Output is correct