oj.uz

Submission #1116932

# Submission time Handle Problem Language Result Execution time Memory
1116932 2024-11-22T15:37:16 Z StefanSebez Speedrun (RMI21_speedrun) C++14
82 / 100
 608 ms 1440 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){

	}
	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){

	}
	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:73:7: warning: variable 'U' set but not used [-Wunused-but-set-variable]
   73 |   int U=start;
      |       ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 864 KB Output is correct
2 Correct 562 ms 1104 KB Output is correct
3 Correct 562 ms 1100 KB Output is correct
4 Correct 545 ms 864 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 928 KB Output is correct
2 Correct 360 ms 1356 KB Output is correct
3 Correct 365 ms 668 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 1440 KB Output is correct
2 Correct 560 ms 668 KB Output is correct
3 Correct 549 ms 1360 KB Output is correct
4 Correct 569 ms 1120 KB Output is correct
5 Correct 594 ms 928 KB Output is correct
6 Correct 549 ms 908 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 543 ms 928 KB Partial solution
2 Partially correct 560 ms 1112 KB Partial solution
3 Partially correct 590 ms 1100 KB Partial solution
4 Partially correct 564 ms 916 KB Partial solution
5 Partially correct 581 ms 1104 KB Partial solution
6 Partially correct 608 ms 916 KB Partial solution
7 Partially correct 551 ms 1148 KB Partial solution