Submission #537003

#	Time	Username	Problem	Language	Result	Execution time	Memory
537003		hmm789	Speedrun (RMI21_speedrun)	C++14	29 / 100	95 ms	804 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
 
void assignHints(int subtask , int N, int A[], int B[]) {
	if(subtask == 1) {
		setHintLen(N);
		for(int i = 1; i < N; i++) {
			setHint(A[i], B[i], 1);
			setHint(B[i], A[i], 1);
		}
	} else if(subtask == 2) {
		setHintLen(20);
		int deg[N], rt = 0;
		memset(deg, 0, sizeof(deg));
		for(int i = 1; i < N; i++) {
			deg[A[i]-1]++; deg[B[i]-1]++;
			if(deg[A[i]-1] == 2) {
				rt = A[i]-1; break;
			} else if(deg[B[i]-1] == 2) {
				rt = B[i]-1; break;
			}
		}
		int pow = 1;
		while(rt > 0) {
			for(int i = 0; i < N; i++) setHint(i+1, pow, rt%2);
			rt /= 2;
			pow++;
		}
	}
}
 
int n;
bool v[1000];
void dfs(int x, int par) {
	v[x] = 1;
	for(int i = 0; i < n; i++) {
		if(getHint(i+1) == 1 && !v[i]) {
			goTo(i+1);
			dfs(i, x);
		}
	}
	if(par != -1) goTo(par+1);
}
 
void speedrun(int subtask , int N, int start) {
	if(subtask == 1) {
		n = N;
		memset(v, 0, sizeof(v));
		dfs(start-1, -1);
	} else if(subtask == 2) {
		int rt = 1;
		for(int i = 1; i <= 20; i++) rt += getHint(i) * pow(2, i-1);
		if(rt != start) goTo(rt);
		for(int i = 0; i < N; i++) {
			if(i+1 == rt) continue;
			goTo(i+1); goTo(rt);
		}
	}
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40