이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
// st0[u][z] = st0[st0[u][z-1]][z-1];
#include <vector>
vector<vector<int>> adj;
vector<vector<int>> radj;
int n = 0;
vector<vector<int>> st0;
vector<vector<int>> st1;
vector<int> visited;
vector<int> h;
// SEGMENT TREE
const int S_ = 262144 * 4 + 5;
vector<vector<int>> tree(S_, vector<int>());
// fast[l/r][node][number] = biggest element <= number in l/r subtree of node
// wait NVM
// For each element inside a segment tree node, we need the O(1) function for that node
//vector<vector<map<int, int>>> fast(2, vector<map<int, int>>(262144 * 2 + 5, map<int, int>()));
// fast[l/r][node][index within that node] = biggest element <= node[index] in l/r subtree of node
vector<vector<vector<int>>> fast(2, vector<vector<int>>(262144 * 4 + 5, vector<int>()));
//vector<vector<vector<int>>> fast(2, vector<vector<int>>(262144 * 2 + 5, vector<int>()));
//int[2][262144 * 2 +5][] fast;
// For each node in the segment tree, we have O(log(n)) numbers
// n logn + n logn + n logn ... logn times
void build(int j, int tl, int tr) {
if (tl == tr) {
tree[j] = {h[tl]};
return;
} else {
int tm = (tl + tr) / 2;
build(j*2, tl, tm);
build(j*2+1, tm+1, tr);
merge(tree[j * 2].begin(), tree[j * 2].end(), tree[j * 2 + 1].begin(), tree[j * 2 + 1].end(), back_inserter(tree[j]));
int pl = 0;
int pr = 0;
for(int x = 0; x < tree[j].size(); x ++){
if(tree[j * 2][pl] == tree[j][x]){
fast[0][j].push_back(pl);
if(x == 0){ fast[1][j].push_back(-1);
} else { fast[1][j].push_back(fast[1][j][fast[1][j].size() - 1]); }
pl += 1;
} else {
fast[1][j].push_back(pr);
if(x == 0){ fast[0][j].push_back(-1);
} else { fast[0][j].push_back(fast[0][j][fast[0][j].size() - 1]); }
pr += 1;
}
}
if(fast[1][j].size() == 0) fast[1][j].push_back(-1);
if(fast[0][j].size() == 0) fast[0][j].push_back(-1);
}
}
/*
void upd(int i, int val, int lbound, int rbound, int j = 1){
if(i < lbound || rbound < i){
return;
}
if(lbound == rbound){
tree[j] = {val};
return;
}
int mid = (lbound + rbound) / 2;
upd(i, val, lbound, mid, j * 2);
upd(i, val, mid+1, rbound, j * 2 + 1);
//tree[j] =min(tree[j * 2], tree[j * 2 + 1]);
//set<int> m;
tree[j].clear();
merge(tree[j * 2].begin(), tree[j * 2].end(), tree[j * 2 + 1].begin(), tree[j * 2 + 1].end(), back_inserter(tree[j]));
fast[0][j].clear();
fast[1][j].clear();
int pl = 0;
int pr = 0;
/*for(int x = 0; x < tree[j * 2].size() + tree[j * 2 + 1].size(); x ++){
tree[j].push_back(
}
/*for(int x = 0; x < tree[j].size(); x ++){
fast[0][tree[j][x]][floor(log2(j))] = 0;
}
pl = 0;
pr = 0;
for(int x = 0; x < tree[j].size(); x ++){
// If tree[j][x] is in the left subtree
if(tree[j * 2][pl] == tree[j][x]){
fast[0][j].push_back(pl);
if(x == 0){
fast[1][j].push_back(-1);
} else {
fast[1][j].push_back(fast[1][j][fast[1][j].size() - 1]);
}
pl += 1;
} else {
// Otherwise it has to be in the right subtree
fast[1][j].push_back(pr);
if(x == 0){
fast[0][j].push_back(-1);
} else {
fast[0][j].push_back(fast[0][j][fast[0][j].size() - 1]);
}
pr += 1;
}
}
}
*/
vector<int> query;
void rangeq(int bound, int ql, int qr, int lbound, int rbound, int j = 1){
if(j == 1){
int left = 0;
int right = rbound;
int m = (left + right) / 2;
int idx = 0;
for (int i = ceil(log2(n)); i >= 0; --i) {
if(idx + (1 << i) < n){
if(tree[1][idx + (1 << i)] <= bound){
//idx = st1[u][i];
idx += (1 << i);
}
}
}
int up = 0;
int mid = (lbound + rbound) / 2;
if(bound >= 0) rangeq(fast[0][j][idx], ql, qr, lbound, mid, j * 2);
if(bound >= 0) rangeq(fast[1][j][idx], ql, qr, mid+1, rbound, j * 2 + 1);
} else {
if(qr < lbound || rbound < ql){
return;
//return INT_MAX;
// DONT DO ANYTHING
} else if(ql <= lbound and rbound <= qr){
//return tree[j];
if(bound >= 0){
query.push_back(tree[j][bound]);
}
//query.push_back(tree[j][bound]);
//query.push_back(bound);
//query.push_back(j);
return;
} else {
int mid = (lbound + rbound) / 2;
if(bound >= 0) rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2);
if(bound >= 0) rangeq(fast[1][j][bound], ql, qr, mid+1, rbound, j * 2 + 1);
}
}
//return min(left_value, right_value);
}
// Construct sparse tables
void dfs0(int u, int v){
if(!visited[u]){
visited[u] = 1;
st0[u][0] = v;
for(int z = 1; z <= ceil(log2(n)); z ++){
st0[u][z] = st0[st0[u][z-1]][z-1];
}
for(int i = 0; i < radj[u].size(); i ++){
int highedge = 1;
for(int j = 0; j < adj[radj[u][i]].size(); j ++){
if(h[adj[radj[u][i]][j]] > h[u]){
highedge = 0;
}
}
if(highedge){
dfs0(radj[u][i], u);
}
}
}
}
void dfs1(int u, int v){
if(!visited[u]){
visited[u] = 1;
st1[u][0] = v;
for(int z = 1; z <= ceil(log2(n)); z ++){
st1[u][z] = st1[st1[u][z-1]][z-1];
}
for(int i = 0; i < radj[u].size(); i ++){
int lowedge = 1;
for(int j = 0; j < adj[radj[u][i]].size(); j ++){
if(h[adj[radj[u][i]][j]] < h[u]){
lowedge = 0;
}
}
if(lowedge){
dfs1(radj[u][i], u);
}
}
}
}
int subtask1 = 1;
vector<int> htt;
void init(int N, vector<int> H) {
n = N;
h = H;
stack<pair<int, int>> s;
vector<vector<int>> adj0(N, vector<int>());
int highest = 0;
int idx = 0;
vector<vector<int>> radj0(N, vector<int>());
// Monotonic stack to construct adjacency list in O(n)
for (int i = 0; i < N; i ++) {
if(i > 0){
if(H[i] != i + 1){
subtask1 = 0;
}
}
while (!s.empty() && s.top().first < H[i]){
s.pop();
}
if (!s.empty()){
adj0[i].push_back(s.top().second);
radj0[s.top().second].push_back(i);
}
s.push({H[i], i});
if(H[i] > highest){
highest = H[i];
idx = i;
}
}
while(!s.empty()){
s.pop();
}
for (int i = N - 1; i >= 0; i --) {
while (!s.empty() && s.top().first < H[i]){
s.pop();
}
if (!s.empty()){
adj0[i].push_back(s.top().second);
radj0[s.top().second].push_back(i);
}
s.push({H[i], i});
}
adj = adj0;
radj = radj0;
vector<vector<int>> st(N, vector<int>(ceil(log2(n)) + 1, 0));
st0 = st;
st1 = st;
vector<int> v(N, 0);
visited = v;
htt = v;
for(int i = 0; i < H.size(); i ++){
htt[H[i] - 1] = i;
}
dfs0(idx, idx);
visited = v;
dfs1(idx, idx);
/*for(int i = 0; i < st1.size(); i ++){
for(int j = 0; j < st1[i].size(); j ++){
cout << h[st1[i][j]] << " ";
} cout << "\n";
}*/
//if(A == B and C != D){
/*for(int i = 0; i < N; i ++){
upd(i, H[i], 0, N);
}*/
build(1, 0, N + 1);
/*for(int i = 0; i < 20; i ++){
cout << i << " | ";
for(int j = 0; j < tree[i].size(); j ++){
cout << tree[i][j] << " ";
} cout << "\n";
}*/
//}
}
int minimum_jumps(int A, int B, int C, int D){
if(C == D){
// In this case, our O(logn) algorithm for subtask 5
query.clear();
//cout << h[6];
rangeq(h[C], A, B, 0, n + 1);
int best = -1;
for(int i = 0; i < query.size(); i ++){
//cout << query[i] << " ";
//if(query[i] <= h[C]){
best = max(best, query[i]);
//}
} //cout << "\n";
//return best;
//}
//cout << best << "\n";
int jumps = 0;
int u = 0;
if(best > 0){
u = htt[best - 1];
} else {
return -1;
}
//return u;
for (int i = ceil(log2(n)); i >= 0; --i) {
if(h[st0[u][i]] < h[C]){
u = st0[u][i];
jumps += (1 << i);
}
}
// If the first sparse table is all we need, we're done
if(st0[u][0] == C){
return jumps + 1;
} else {
// Otherwise start at the next sparse table
for (int i = ceil(log2(n)); i >= 0; --i) {
if(h[st1[u][i]] < h[C]){
u = st1[u][i];
jumps += (1 << i);
}
}
if(st1[u][0] == C){
return jumps + 1;
}
}
return -1;
} else {
if(subtask1){
return C - B;
} else {
queue<pair<int, int>> q;
for(int i = A; i <= B; i ++){
q.push({0, i});
}
int node = 0; int dist = 0;
vector<int> vi(n, 0);
while(!q.empty()){
node = q.front().second;
dist = q.front().first;
//cout << node << "\n";
q.pop();
if(node >= C && node <= D){
return dist;
//break;
}
if(!vi[node]){
vi[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q.push({dist + 1, adj[node][i]});
}
}
}
return -1;
}
}
return -1;
}
/*
g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp
7 6
3 2 1 6 4 5 7
0 3 4 4
0 4 4 4
0 5 4 4
0 3 5 5
0 4 5 5
0 5 5 5
if(A == B and C == D){
int jumps = 0;
int u = A;
for (int i = ceil(log2(n)); i >= 0; --i) {
if(h[st0[u][i]] < h[C]){
u = st0[u][i];
jumps += (1 << i);
}
}
// If the first sparse table is all we need, we're done
if(st0[u][0] == C){
return jumps + 1;
} else {
// Otherwise start at the next sparse table
for (int i = ceil(log2(n)); i >= 0; --i) {
if(h[st1[u][i]] < h[C]){
u = st1[u][i];
jumps += (1 << i);
}
}
if(st1[u][0] == C){
return jumps + 1;
}
}
return -1;
// Otherwise, if it's subtask 1, we do our dumb solution
} else if(subtask1){
return C - B;
// Subtask 6 - wavelet tree
} else if(C == D){
cout << 100;
query.clear();
//rangeq(C, A, B, 0, n);
for(int i = 0; i < query.size(); i ++){
cout << query[i] << " ";
} cout << "\n";
// Now it's only subtask 2, 3 or 4 so we do BFS
} else {
//return u;
if(jumps){
return jumps + 1;
} else {
return 0;
}
queue<pair<int, int>> q;
for(int i = A; i <= B; i ++){
q.push({0, i});
}
int node = 0; int dist = 0;
vector<int> vi(n, 0);
while(!q.empty()){
node = q.front().second;
dist = q.front().first;
//cout << node << "\n";
q.pop(); x
if(node >= C && node <= D){
return dist;
//break;
}
if(!vi[node]){
vi[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q.push({dist + 1, adj[node][i]});
}
}
}
return -1;
}
*/
컴파일 시 표준 에러 (stderr) 메시지
jumps.cpp:76:5: warning: "/*" within comment [-Wcomment]
76 | /*for(int x = 0; x < tree[j * 2].size() + tree[j * 2 + 1].size(); x ++){
|
jumps.cpp:79:5: warning: "/*" within comment [-Wcomment]
79 | /*for(int x = 0; x < tree[j].size(); x ++){
|
jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int x = 0; x < tree[j].size(); x ++){
| ~~^~~~~~~~~~~~~~~~
jumps.cpp: In function 'void rangeq(int, int, int, int, int, int)':
jumps.cpp:115:13: warning: unused variable 'm' [-Wunused-variable]
115 | int m = (left + right) / 2;
| ^
jumps.cpp:126:13: warning: unused variable 'up' [-Wunused-variable]
126 | int up = 0;
| ^~
jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:162:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int i = 0; i < radj[u].size(); i ++){
| ~~^~~~~~~~~~~~~~~~
jumps.cpp:164:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int j = 0; j < adj[radj[u][i]].size(); j ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:182:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for(int i = 0; i < radj[u].size(); i ++){
| ~~^~~~~~~~~~~~~~~~
jumps.cpp:184:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int j = 0; j < adj[radj[u][i]].size(); j ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:249:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | for(int i = 0; i < H.size(); i ++){
| ~~^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:282:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
282 | for(int i = 0; i < query.size(); i ++){
| ~~^~~~~~~~~~~~~~
jumps.cpp:343:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
343 | for(int i = 0; i < adj[node].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |