oj.uz

Submission #1116937

# Submission time Handle Problem Language Result Execution time Memory
1116937 2024-11-22T15:42:26 Z StefanSebez Speedrun (RMI21_speedrun) C++14
90 / 100
 586 ms 1616 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(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) {
	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(U!=u){
				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 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 574 ms 916 KB Output is correct
2 Correct 567 ms 924 KB Output is correct
3 Correct 586 ms 848 KB Output is correct
4 Correct 521 ms 884 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1032 KB Output is correct
2 Correct 189 ms 916 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 1364 KB Output is correct
2 Correct 323 ms 1372 KB Output is correct
3 Correct 371 ms 1104 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 1108 KB Output is correct
2 Correct 515 ms 1616 KB Output is correct
3 Correct 550 ms 1108 KB Output is correct
4 Correct 525 ms 1108 KB Output is correct
5 Correct 554 ms 924 KB Output is correct
6 Correct 558 ms 856 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 527 ms 848 KB Partial solution
2 Partially correct 526 ms 924 KB Partial solution
3 Partially correct 573 ms 700 KB Partial solution
4 Partially correct 494 ms 928 KB Partial solution
5 Partially correct 447 ms 1108 KB Partial solution
6 Partially correct 472 ms 1092 KB Partial solution
7 Partially correct 498 ms 708 KB Partial solution