Submission #70144

#	Time	Username	Problem	Language	Result	Execution time	Memory
70144		Inovak	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2062 ms	22484 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];

inline void go() {
    for(int i = 1; i <= n; i++) d[i] = inf;
    d[s] = 0;
    priority_queue < pair<int,int> > q;
	q.push (mk (0, s));
	while (!q.empty()) {
		int v = q.top().sc,  cur_d = -q.top().first;
		q.pop();
		if (cur_d > d[v])  continue;

        for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				q.push (make_pair (-d[to], to));
			}
		}
	}

}

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);
    }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:45: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:47: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:86: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: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55