oj.uz

Submission #70144

# Submission time Handle Problem Language Result Execution time Memory
70144 2018-08-22T11:49:39 Z Inovak Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 22484 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5172 KB Output is correct
4 Correct 8 ms 5252 KB Output is correct
5 Correct 8 ms 5252 KB Output is correct
6 Correct 8 ms 5252 KB Output is correct
7 Correct 7 ms 5252 KB Output is correct
8 Correct 8 ms 5252 KB Output is correct
9 Correct 6 ms 5252 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5460 KB Output is correct
2 Correct 633 ms 12776 KB Output is correct
3 Correct 719 ms 12984 KB Output is correct
4 Correct 751 ms 13236 KB Output is correct
5 Correct 814 ms 13560 KB Output is correct
6 Correct 909 ms 14080 KB Output is correct
7 Correct 1268 ms 15196 KB Output is correct
8 Correct 268 ms 15196 KB Output is correct
9 Correct 331 ms 16060 KB Output is correct
10 Correct 302 ms 16060 KB Output is correct
11 Correct 598 ms 16252 KB Output is correct
12 Correct 640 ms 16844 KB Output is correct
13 Correct 638 ms 17172 KB Output is correct
14 Correct 626 ms 17976 KB Output is correct
15 Correct 628 ms 18536 KB Output is correct
16 Correct 593 ms 18988 KB Output is correct
17 Correct 1277 ms 20288 KB Output is correct
18 Correct 1316 ms 20864 KB Output is correct
19 Correct 1110 ms 21720 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 21720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 22484 KB Time limit exceeded
2 Halted 0 ms 0 KB -