제출 #828959

#제출 시각아이디문제언어결과실행 시간메모리
828959yeyso밀림 점프 (APIO21_jumps)C++14
23 / 100
1569 ms309856 KiB
#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<int>> RMQ; /* THE PLAN To find the best tree in the range [A, B] - Find the rightmost tree in the range that is taller than C, call it X using a Segtree that supports range rightmost threshold queries! Then a segtree that supports range upper bound queries! A != B but C = D A ... B Let X = rightmost tree between A and B that is taller than C Now use range upper bound to find tallest tree between X and B that is shorter than C And then do RMQ(C) for the tree we want to start at Then we need to find the fastest way to get to (C -- D) Solve the problem in reverse - Then do the range upper bound query within the range [X, B] */ //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 int fast_log(int x){ return x ? __builtin_clzll(1) - __builtin_clzll(x) : -1; } 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); } } vector<int> query; int rmq0(int l, int r){ int i = fast_log(r - l + 1); return max(RMQ[i][l], RMQ[i][r - (1 << i) + 1]); } int qu = 0; void rightmost(int threshold, int ql, int qr, int lbound, int rbound, int j = 1){ int mid = (lbound + rbound) / 2; if(lbound == rbound){ qu = max(qu, lbound); return; } int call = 0; if(rmq0(mid+1, rbound) >= threshold){ if(ql <= rbound and qr >= mid + 1){ call = 1; rightmost(threshold, ql, qr, mid+1, rbound, j * 2 + 1); } } if(rmq0(lbound, mid) >= threshold){ if(!call){ if(ql <= mid and qr >= lbound){ rightmost(threshold, ql, qr, lbound, mid, j * 2); } } } } void rangeq(int bound, int ql, int qr, int lbound, int rbound, int j = 1){ if(qr < lbound || rbound < ql){ //return INT_MAX; // DONT DO ANYTHING } else if(ql <= lbound and rbound <= qr){ if(bound >= 0){ query.push_back(tree[j][bound]); } } else { int mid = (lbound + rbound) / 2; if(bound >= 0){ rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2); rangeq(fast[1][j][bound], ql, qr, mid+1, rbound, j * 2 + 1); } } } // 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)); vector<vector<int>> rmqt(ceil(log2(n))+1, vector<int>(N, 0)); st0 = st; st1 = st; RMQ = rmqt; for(int j = 0; j < n; j ++){ RMQ[0][j] = H[j]; } for(int i = 1; i <= ceil(log2(n)); i ++){ for(int j = 0; j < n; j ++){ RMQ[i][j] = max(RMQ[i-1][j], RMQ[i-1][j + (1 << (i - 1))]); } } 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); build(1, 0, N + 1); } int minimum_jumps(int A, int B, int C, int D){ qu = -1; rightmost(h[C], A, B, 0, n); //return rmq0(A, B); int start = rmq0(max(qu, A), B); //return qu; if(C == D){ int jumps = 0; int u = htt[start - 1]; 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; } /*{ 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; } /* The rightmost tree within range that is taller than g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp 7 3 3 7 5 6 4 2 1 0 1 6 6 0 2 6 6 0 3 6 6 0 4 4 4 0 5 4 4 0 6 4 4 3 6 5 5 4 6 5 5 5 6 5 5 6 6 6 6 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: In function 'void build(int, int, int)':
jumps.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int x = 0; x < tree[j].size(); x ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:137:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:155:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:157:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:224:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int i = 0; i < H.size(); i ++){
      |                    ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...