oj.uz

답안 #504809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
504809 2022-01-10T09:00:48 Z hohohaha Speedrun (RMI21_speedrun) C++14
100 / 100
 299 ms 10260 KB 
#include "speedrun.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#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;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
//#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

//#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int maxn = 2e5 + 5; 
int assign_par[maxn], assign_nxt[maxn]; 
vector<int> g[maxn]; 
int assign_last; 
void dfs(int u, int p) { 
	assign_nxt[assign_last] = u; assign_last = u; 
	assign_par[u] = p; 
	for(int v: g[u]) { 
	 	if(v - p) { 
	 		dfs(v, u); 
	 	}
	 }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	int n = N; 
	fori(i,1,n - 1) { 
		g[A[i]].eb(B[i]); 
		g[B[i]].eb(A[i]);
	}
	dfs(1,0); 
	setHintLen(20); 
	fori(i,1,n) { 
		fori(bit, 0, 9) { 
		 	setHint(i, bit + 1, assign_par[i] >> bit & 1); 
		 }
		 fori(bit, 0, 9) { 
		 	setHint(i, bit + 11, assign_nxt[i] >> bit & 1); 
		 }
	}
}

int speed_par[maxn]; 
int speed_nxt[maxn]; 
void prep_info(int now) { 
	if(!speed_par[now] and !speed_nxt[now]) { 
		fori(bit, 0, 9) { 
		 	int v = getHint(bit + 1); 
		 	speed_par[now] ^= (v << bit); 
		 }
		 fori(bit, 0, 9) { 
		 	int v = getHint(bit + 11); 
		 	speed_nxt[now] ^= (v << bit); 
		 }
//		 cout << now << ": " << speed_par[now] << speed_nxt[now] << endl; 
	}
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	int n = N; int now = start;
	prep_info(start);  
	while(now != 1) {
		prep_info(now); 
		goTo(speed_par[now]); now = speed_par[now]; 
//		 cout << "now: " << now << endl; 
	}
	fori(i,2,n) { 
		 prep_info(now); 
//		 cout << "now: " << now << sp << speed_par[now] << endl; 
		 int nxt = speed_nxt[now]; 
//		 cout << now << " - > " << nxt << endl; 
		 while(1) { 
		 	if(goTo(nxt))  { 
			 	now = nxt; 
			 	break; 
			 }
			 else { 
			  	goTo(speed_par[now]); 
				now = speed_par[now]; 
			}
		}
	}
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 10132 KB Output is correct
2 Correct 218 ms 10132 KB Output is correct
3 Correct 142 ms 10124 KB Output is correct
4 Correct 204 ms 10188 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 10112 KB Output is correct
2 Correct 239 ms 10124 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 10208 KB Output is correct
2 Correct 269 ms 10076 KB Output is correct
3 Correct 202 ms 10192 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 10176 KB Output is correct
2 Correct 299 ms 10132 KB Output is correct
3 Correct 208 ms 10132 KB Output is correct
4 Correct 279 ms 10124 KB Output is correct
5 Correct 233 ms 10120 KB Output is correct
6 Correct 262 ms 10184 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 10204 KB Output is correct
2 Correct 143 ms 10132 KB Output is correct
3 Correct 181 ms 10204 KB Output is correct
4 Correct 265 ms 10128 KB Output is correct
5 Correct 253 ms 10260 KB Output is correct
6 Correct 269 ms 10132 KB Output is correct
7 Correct 205 ms 10232 KB Output is correct