oj.uz

Submission #537019

# Submission time Handle Problem Language Result Execution time Memory
537019 2022-03-14T09:44:04 Z hmm789 Speedrun (RMI21_speedrun) C++14
48 / 100
 168 ms 800 KB 
#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++;
		}
	} else if(subtask == 3) {
		setHintLen(20);
		bool set[N];
		memset(set, 0, sizeof(set));
		int idx = 0, tmp;
		for(int i = 1; i < N; i++) {
			if(set[A[i]-1]) idx = 11;
			else idx = 1;
			tmp = B[i];
			while(tmp > 0) {
				setHint(A[i], idx, tmp%2);
				tmp /= 2;
				idx++;
			}
			if(set[B[i]-1]) idx = 11;
			else idx = 1;
			tmp = A[i];
			while(tmp > 0) {
				setHint(B[i], idx, tmp%2);
				tmp /= 2;
				idx++;
			}
			set[A[i]-1] = 1; set[B[i]-1] = 1;
		}
	}
}

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 dfs2(int x, int par) {
	v[x] = 1;
	int to[2];
	for(int i = 0; i < 2; i++) {
		to[i] = -1;
		for(int j = 10*i+1; j <= 10*i+10; j++) to[i] += getHint(j) * pow(2, (j-1)%10);
	}
	for(int i = 0; i < 2; i++) {
		if(to[i] == -1) continue;
		if(!v[to[i]]) {
			goTo(to[i]+1);
			dfs2(to[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);
		}
	} else if(subtask == 3) {
		n = N;
		memset(v, 0, sizeof(v));
		dfs2(start-1, -1);
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 796 KB Output is correct
2 Correct 34 ms 800 KB Output is correct
3 Correct 38 ms 796 KB Output is correct
4 Correct 41 ms 688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 684 KB Output is correct
2 Correct 75 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 800 KB Output is correct
2 Correct 168 ms 676 KB Output is correct
3 Correct 156 ms 676 KB Output is correct

Subtask #4
0.0 / 12.0

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

Subtask #5
0.0 / 40.0

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