oj.uz

Submission #537003

# Submission time Handle Problem Language Result Execution time Memory
537003 2022-03-14T09:21:48 Z hmm789 Speedrun (RMI21_speedrun) C++14
29 / 100
 95 ms 804 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++;
		}
	}
}
 
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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 792 KB Output is correct
2 Correct 41 ms 804 KB Output is correct
3 Correct 43 ms 740 KB Output is correct
4 Correct 46 ms 804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 708 KB Output is correct
2 Correct 90 ms 672 KB Output is correct

Subtask #3
0.0 / 19.0

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

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 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -