oj.uz

Submission #921519

# Submission time Handle Problem Language Result Execution time Memory
921519 2024-02-04T04:48:18 Z pavement Speedrun (RMI21_speedrun) C++17
100 / 100
 128 ms 2292 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair

using ii = pair<int, int>;

namespace stage_1 {
	int down[1005], nxt[1005], par[1005];
	vector<int> adj[1005];

	void dfs(int u, int e = 0) {
		par[u] = e;
		vector<int> chd;
		for (auto v : adj[u]) if (v != e) {
			chd.pb(v);
			dfs(v, u);
		}
		down[u] = (chd.empty() ? 0 : chd[0]);
		for (int i = 0; i + 1 < (int)chd.size(); i++) {
			nxt[chd[i]] = chd[i + 1];
		}
	}
};

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);
	
	if (N == 1) {
		return;
	}
	
	for (int i = 1; i < N; i++) {
		stage_1::adj[A[i]].pb(B[i]);
		stage_1::adj[B[i]].pb(A[i]);
	}
	stage_1::dfs(1);
	for (int i = 1; i <= N; i++) {
		if (stage_1::nxt[i] == 0) {
			if (i == 1) {
				stage_1::nxt[i] = N + 1;
			} else {
				stage_1::nxt[i] = stage_1::par[stage_1::par[i]];
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 10; j++) {
			setHint(i, j, !!(stage_1::down[i] & (1 << (j - 1))));
		}
		for (int j = 11; j <= 20; j++) {
			setHint(i, j, !!(stage_1::nxt[i] & (1 << (j - 11))));
		}
	}
}

namespace stage_2 {
	int N;
	bool vis[1005];
	
	ii unpack() {
		int ret_down = 0, ret_nxt = 0;
		for (int i = 1; i <= 20; i++) {
			if (getHint(i)) {
				if (i <= 10) {
					ret_down |= (1 << (i - 1));
				} else {
					ret_nxt |= (1 << (i - 11));
				}
			}
		}
		return mp(ret_down, ret_nxt);
	};
	
	void dfs(int u, int e = 0) {
		vis[u] = 1;
		
		int tmp_2 = unpack().second;
		
		if (tmp_2 && tmp_2 != N + 1 && !vis[tmp_2]) {
			assert(e);
			goTo(e);
			goTo(tmp_2);
			dfs(tmp_2, e);
			goTo(e);
			goTo(u);
		}
		
		int tmp_1 = unpack().first;
		
		if (tmp_1 == 0) {
			return;
		}
		
		goTo(tmp_1);
		dfs(tmp_1, u);
		goTo(u);
	}
};

void speedrun(int subtask, int N, int start) {
	if (N == 1) {
		return;
	}
	
	stage_2::N = N;
	
	auto [start_down, start_nxt] = stage_2::unpack();
	
	if (start_down == 0) {
		for (int i = 1; i <= N; i++) {
			if (goTo(i)) {
				start = i;
				break;
			}
		}
	}
	
	int u = start;
	
	while (1) {
		auto [cur_down, cur_nxt] = stage_2::unpack();
		
		assert(cur_down);
		
		int v = cur_down, prv_v = -1;
		
		while (1 <= v && v <= N && goTo(v)) {
			prv_v = v;
			v = stage_2::unpack().second;
			goTo(u);
		}
		
		goTo(prv_v);
		u = prv_v;
		
		if (v == 0) {
			break;
		}
	}
	
	assert(goTo(1));
	
	stage_2::dfs(1);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1364 KB Output is correct
2 Correct 128 ms 1392 KB Output is correct
3 Correct 95 ms 1368 KB Output is correct
4 Correct 99 ms 1108 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 1884 KB Output is correct
2 Correct 113 ms 2292 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1536 KB Output is correct
2 Correct 100 ms 2044 KB Output is correct
3 Correct 98 ms 1368 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1888 KB Output is correct
2 Correct 114 ms 1536 KB Output is correct
3 Correct 128 ms 1620 KB Output is correct
4 Correct 101 ms 1616 KB Output is correct
5 Correct 110 ms 1368 KB Output is correct
6 Correct 113 ms 1636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1372 KB Output is correct
2 Correct 106 ms 1616 KB Output is correct
3 Correct 107 ms 1520 KB Output is correct
4 Correct 94 ms 1880 KB Output is correct
5 Correct 100 ms 1544 KB Output is correct
6 Correct 90 ms 1624 KB Output is correct
7 Correct 110 ms 1648 KB Output is correct