제출 #821595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821595		yeyso	밀림 점프 (APIO21_jumps)	C++14	0 / 100	272 ms	179872 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#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;
void dfs0(int u, int v){
    if(!visited[u]){
        visited[u] = 1;
        st0[u][0] = v;
        //cout << h[u] << " " << h[v] << "\n";
        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;
                    //break;
                }
            }
            if(highedge){
                dfs0(radj[u][i], u);
            }
        }
    }
}
void dfs1(int u, int v){
    if(!visited[u]){
        visited[u] = 1;
        st1[u][0] = v;
        //cout << h[u] << " " << h[v] << "\n";
        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;
            if(adj[radj[u][i]].size() > 1){
                for(int j = 0; j < adj[radj[u][i]].size(); j ++){
                    if(h[adj[radj[u][i]][j]] < h[u]){
                        lowedge = 0;
                        //break;
                    }
                }
                if(lowedge){
                    dfs1(radj[u][i], u);
                }
            }
        }
    }
}
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>());
    for (int i = 0; i < N; 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});

        if(H[i] > highest){
            highest = H[i];
            idx = i;
        }
    }
    while(!s.empty()){
        s.pop();
    }
    for (int i = N; 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)), 0));
    st0 = st;
    st1 = st;
    vector<int> v(N, 0);
    visited = v;
    dfs0(idx, idx);
    visited = v;
    dfs1(idx, idx);
}

int minimum_jumps(int A, int B, int C, int D) {

    int res = 0;
    int u = A;
    for (int i = ceil(log2(n)); i >= 0; --i) {
        if(h[st0[u][i]] < h[C]){
            u = st0[u][i];
            res += (1 << i);
        }
    }
    // If the first sparse table is all we need, we're done
    if(st0[u][0] == C){
        return res + 1;
    } else {
        // Add one jump to start at the next sparse table
        u = st0[u][0];
        res += 1;
        for (int i = ceil(log2(n)); i >= 0; --i) {
            if(h[st1[u][i]] < h[C]){
                u = st1[u][i];
                res += (1 << i);
            }
        }

        if(st1[u][0] == C){
            return res + 1;
        }
    }
    return -1;
    //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> v(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(!v[node]){
            v[node] = 1;
            for(int i = 0; i < adj[node].size(); i ++){
                q.push({dist + 1, adj[node][i]});
            }
        }
    }*/
}
/*
g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp

7 5
3 2 1 6 4 5 7
4 4 6 6
1 1 3 3
0 0 1 1
2 2 6 6
3 3 5 5

0  1  2  3  4  5  6 7 8 9 10 11 12 3 4 5 16 17 18 19
40 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
4 4 19 19
14 14 0 0
3 3 9 9
4 4 3 3
2 2 10 10
3 3 15 15
4 4 11 11
0 0 40 40
0 0 38 38
3 3 37 37
*/

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:20:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:22:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:45:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19