제출 #70135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70135		Inovak	Railway Trip (JOI17_railway_trip)	C++14	5 / 100	2072 ms	18708 KiB

railway_trip

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define ll long long
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5+10;
const int inf = 1e9+7;

int n, k, q, s, f;
int L[N], l[N], r[N];
int d[N];
vector <pair <int, int> > g[N];

void go() {
    for(int i = 1; i <= n; i++) d[i] = inf;
    d[s] = 0;
    set <pair <int, int> > st;
    st.insert(mk(0, s));
    while(!st.empty()) {
        int v = st.begin()->sc;
        st.erase(st.begin());
        for(auto i : g[v]) {
            if(d[i.fr] > d[v] + i.sc) {
                st.erase(mk(d[i.fr], i.fr));
                st.insert(mk(d[i.fr] = d[v] + i.sc, i.fr));
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &k, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &L[i]);
    }
    stack <int> st, si;
    st.push(inf);
    si.push(0);
    for(int i = 1; i <= n; i++) {
        while(st.top() < L[i]) {
            st.pop();
            si.pop();
        }
        l[i] = si.top();
        st.push(L[i]);
        si.push(i);
    }
    while(!st.empty()) st.pop(), si.pop();
    st.push(inf);
    si.push(n+1);
    for(int i = n; i >= 1; i--) {
        while(st.top() < L[i]) {
            st.pop();
            si.pop();
        }
        r[i] = si.top();
        st.push(L[i]);
        si.push(i);
    }

    for(int i = 1; i <= n; i++) {
        if(l[i] != 0) {
            g[i].pb(mk(l[i], 1));
            g[l[i]].pb(mk(i, 1));
        }
        if(r[i] != n+1) {
            g[i].pb(mk(r[i], 1));
            g[r[i]].pb(mk(i, 1));
        }
    }

    while(q--) {
        scanf("%d%d", &s, &f);
        if(s == f) {puts("0");continue;}
        go();
        printf("%d\n", d[f] - 1);
    }
}

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

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &L[i]);
         ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s, &f);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55