Submission #823945

#TimeUsernameProblemLanguageResultExecution timeMemory
823945yeysoRainforest Jumps (APIO21_jumps)C++14
Compilation error
0 ms0 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 * 2 + 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 * 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(vector<int> a, int j, int tl, int tr) { if (tl == tr) { tree[j] = {a[tl]}; } else { int tm = (tl + tr) / 2; build(a, j*2, tl, tm); build(a, 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; } } } } /* 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(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; rangeq(fast[0][j][bound], ql, qr, lbound, mid, j * 2); 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); }*/ if(n < 100000) build(H, 1, 0, N); /*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) { // In this case, our O(logn) algorithm for subtask 5 query.clear(); //cout << h[6]; rangeq(h[C], A, B, 0, n); int best = 0; for(int i = 0; i < query.size(); i ++){ //cout << query[i] << " "; if(query[i] <= h[C]){ best = max(best, query[i]); } } //cout << "\n"; //cout << best << "\n"; int jumps = 0; int u = htt[best - 1]; int jumps = 0; int u = B; //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; //return -1; } /* g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp 7 7 3 2 1 6 4 5 7 0 3 0 0 0 3 1 1 0 3 2 2 0 3 3 3 0 3 4 4 0 3 5 5 0 3 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(); 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; } */

Compilation message (stderr)

jumps.cpp:70:5: warning: "/*" within comment [-Wcomment]
   70 |     /*for(int x = 0; x < tree[j * 2].size() + tree[j * 2 + 1].size(); x ++){
      |      
jumps.cpp:73:5: warning: "/*" within comment [-Wcomment]
   73 |     /*for(int x = 0; x < tree[j].size(); x ++){
      |      
jumps.cpp: In function 'void build(std::vector<int>, int, int, int)':
jumps.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         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:222:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |     for(int i = 0; i < H.size(); i ++){
      |                    ~~^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:255:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |         for(int i = 0; i < query.size(); i ++){
      |                        ~~^~~~~~~~~~~~~~
jumps.cpp:265:9: error: redeclaration of 'int jumps'
  265 |     int jumps = 0;
      |         ^~~~~
jumps.cpp:262:13: note: 'int jumps' previously declared here
  262 |         int jumps = 0;
      |             ^~~~~
jumps.cpp:266:9: error: redeclaration of 'int u'
  266 |     int u = B;
      |         ^
jumps.cpp:263:13: note: 'int u' previously declared here
  263 |         int u = htt[best - 1];
      |             ^