제출 #933603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933603		vjudge1	Speedrun (RMI21_speedrun)	C++17	29 / 100	99 ms	2036 KiB

speedrun

// Problem: B - Speedrun
// Contest: Virtual Judge - PES segundo examen de práctica febrero 2024
// URL: https://vjudge.net/contest/612265#problem/B
// Memory Limit: 512 MB
// Time Limit: 3500 ms
// Start: 25-02-2024 15:56:28

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

#define gcd(x, y) __gcd(x, y)
#define mcm(x, y) abs((x) * (y)) / gcd(x, y)
#define all(x)    begin(x), end(x)
#define pb(x)     push_back(x)
#define endl      '\n'

#ifdef DEBUG
int A[] = {0, 1, 1, 1, 1}, B[] = {0, 2, 3, 4, 5};
int N     = 5;
int start = 2;

ll   LEN;
bool hints[500][500] = {{}};
ll   currNode        = start;

void setHintLen(int l) { LEN = l; };
void setHint(int i, int j, bool b) { hints[i][j] = b; };
int  getLength() { return LEN; };
bool getHint(int j) { return hints[currNode][j]; };
bool goTo(int x) {
	for (int i = 1; i < N; i++) {
		ll a = A[i], b = B[i];
		if ((a == currNode && b == x) || (a == x && b == currNode)) {
			currNode = x;
			cout << currNode << ' ';
			return true;
		}
	}
	return false;
};

#else
void setHintLen(int l);
void setHint(int i, int j, bool b);
int  getLength();
bool getHint(int j);
bool goTo(int x);
#endif

void assign1(int subtask, int N, int A[], int B[]) {
	setHintLen(N);

	vector<vector<ll>> g(N + 1);
	for (int i = 1; i < N; i++) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}

	for (int i = 1; i <= N; i++)
		for (ll& nei : g[i]) setHint(i, nei, true);
}

void dfs1(ll idx, ll p, ll N) {
	for (int i = 1; i <= N; i++) {
		bool x = getHint(i);
		if (!x || i == p) continue;
		goTo(i);
		dfs1(i, idx, N);
	}
	if (p != -1) goTo(p);
}

void assign2(int subtask, int N, int A[], int B[]) {
	setHintLen(20);

	vector<vector<ll>> g(N + 1);
	for (int i = 1; i < N; i++) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}

	ll mid = 0;
	for (int i = 1; i <= N; i++)
		if (g[i].size() > 1) mid = i;

	bitset<20> flag(mid);
	flag[19] = true;

	for (int i = 1; i <= N; i++) {
		if (i == mid) continue;
		for (int idx = 0; idx < 20; idx++)
			setHint(i, idx + 1, flag[idx]);
	}
}

void move2(ll N, ll start) {
	// Check if middle
	ll mid = start;
	if (getHint(20)) {
		ll curr = 0;
		for (int i = 19; i; i--) {
			curr <<= 1;
			bool x = getHint(i);
			curr |= x;
		}
		mid = curr;
	}
	if (start != mid) goTo(mid);

	for (int i = 1; i <= N; i++) {
		goTo(i);
		goTo(mid);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	if (subtask == 1) assign1(subtask, N, A, B);
	if (subtask == 2) assign2(subtask, N, A, B);
}

void speedrun(int subtask, int N, int start) {
	if (subtask == 1) dfs1(start, -1, N);
	if (subtask == 2) move2(N, start);
}
#ifdef DEBUG
int main() {
	cout << start << ' ';
	assignHints(2, N, A, B);
	speedrun(2, N, start);

	cout << currNode;
}
#endif

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