oj.uz

Submission #1116931

# Submission time Handle Problem Language Result Execution time Memory
1116931 2024-11-22T15:31:16 Z StefanSebez Speedrun (RMI21_speedrun) C++14
63 / 100
 606 ms 1356 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;
		for(int i=1;i<=n;i++) if(E[i].size()==1) {root=i;break;}
		//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;
      |       ^
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:35:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   DFS1(root,0);
      |   ~~~~^~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 924 KB Output is correct
2 Correct 534 ms 1356 KB Output is correct
3 Correct 579 ms 1116 KB Output is correct
4 Correct 559 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
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 668 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 1100 KB Output is correct
2 Correct 573 ms 1116 KB Output is correct
3 Correct 574 ms 860 KB Output is correct
4 Correct 568 ms 860 KB Output is correct
5 Correct 527 ms 852 KB Output is correct
6 Correct 551 ms 856 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 567 ms 848 KB Partial solution
2 Partially correct 544 ms 856 KB Partial solution
3 Partially correct 576 ms 1180 KB Partial solution
4 Partially correct 559 ms 1352 KB Partial solution
5 Partially correct 550 ms 856 KB Partial solution
6 Partially correct 606 ms 848 KB Partial solution
7 Partially correct 571 ms 1276 KB Partial solution