oj.uz

답안 #504692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
504692 2022-01-10T07:39:25 Z hollwo_pelw Speedrun (RMI21_speedrun) C++17
100 / 100
 122 ms 848 KB 
/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

#ifdef hollwo_pelw_local
signed main(){
	FAST_IO("input.inp", "output.out", "error.err");
	
	auto start = chrono::steady_clock::now();
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
	
	return 0;
}
#endif

const int N = 1005;

vector<int> adj[N];

#ifdef hollwo_pelw_local

namespace interactive {
	int hint[N], size, fail_cnt, curnode;

	void setHintLen(int l) {
		size = l, fail_cnt = 0;
	}

	void setHint(int i, int j, bool b) {
		assert(1 <= j && j <= size);
		if (b) hint[i] |= 1 << j - 1;
	}

	int getLength() {
		return size;
	}

	bool getHint(int j) {
		assert(1 <= j && j <= size);
		return hint[curnode] >> (j - 1) & 1;
	}

	bool goTo(int x) {
		for (auto v : adj[curnode])
			if (v == x) {
				curnode = v;
				return 1;
			}
		++ fail_cnt;
		if (fail_cnt > 2000)
			assert(0);
		return 0;
	}
}

using namespace interactive;

#else

#include "speedrun.h"

#endif

vector<int> ord;
int par[N];

void pre_dfs(int u, int p) {
	ord.push_back(u);
	par[u] = p;

	for (auto v : adj[u]) if (v != p) {
		pre_dfs(v, u);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	for (int i = 1; i < N; i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	setHintLen(20);
	pre_dfs(1, 0);
	ord.push_back(0);

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 10; j++)
			if (par[i] >> j & 1)
				setHint(i, j + 1, 1);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 10; j++)
			if (ord[i] >> j & 1)
				setHint(ord[i - 1], j + 11, 1);
	}
}

inline int getpar() {
	int res = 0;
	for (int i = 0; i < 10; i++)
		if (getHint(i + 1))
			res |= 1 << i;
	return res;
}

inline int getnxt() {
	int res = 0;
	for (int i = 0; i < 10; i++)
		if (getHint(i + 11))
			res |= 1 << i;
	return res;
}

void speedrun(int subtask, int N, int start) {
	int cur = start;
	while (int p = getpar()) {
		if (goTo(p)) cur = p;
	}
	while (int nxt = getnxt()) {
		if (!nxt) return ;
		while (!goTo(nxt))
			if (goTo(getpar()))
				cur = getpar();
		cur = nxt;
	}
}

void Hollwo_Pelw() {
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int N, curnode; cin >> N;
	int A[N], B[N];
	for (int i = 1; i < N; i++)
		cin >> A[i] >> B[i];
	assignHints(1, N, A, B);

	speedrun(1, N, curnode = rng() % N + 1);
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:145:6: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  145 |  int cur = start;
      |      ^~~
speedrun.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
speedrun.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
speedrun.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 672 KB Output is correct
2 Correct 82 ms 660 KB Output is correct
3 Correct 117 ms 696 KB Output is correct
4 Correct 97 ms 664 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 696 KB Output is correct
2 Correct 82 ms 660 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 712 KB Output is correct
2 Correct 97 ms 848 KB Output is correct
3 Correct 113 ms 676 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 692 KB Output is correct
2 Correct 112 ms 700 KB Output is correct
3 Correct 97 ms 704 KB Output is correct
4 Correct 108 ms 696 KB Output is correct
5 Correct 99 ms 660 KB Output is correct
6 Correct 117 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 744 KB Output is correct
2 Correct 104 ms 828 KB Output is correct
3 Correct 103 ms 704 KB Output is correct
4 Correct 122 ms 676 KB Output is correct
5 Correct 81 ms 660 KB Output is correct
6 Correct 112 ms 708 KB Output is correct
7 Correct 110 ms 676 KB Output is correct