oj.uz

Submission #90376

# Submission time Handle Problem Language Result Execution time Memory
90376 2018-12-21T12:18:21 Z Alexa2001 Railway Trip (JOI17_railway_trip) C++17
20 / 100
 239 ms 16192 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;

int n, q, k;
int a[Nmax], dist[Nmax], st[Nmax];
vector<int> v[Nmax];

int dijkstra(int x, int y)
{
    queue<int> q;
    int i;
    for(i=1; i<=n; ++i) dist[i] = -1;

    dist[x] = 0;
    q.push(x);

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : v[node])
            if(dist[it] == -1)
            {
                dist[it] = dist[node] + 1;
                q.push(it);
            }
    }
    return dist[y];
}

void add_edge(int x, int y)
{
    v[x].push_back(y);
    v[y].push_back(x);
}

void brute()
{
    int i, nr = 0;
    for(i=1; i<=n; ++i)
    {
        while(nr && a[st[nr]] < a[i]) --nr;
        if(nr) add_edge(i, st[nr]);
        st[++nr] = i;
    }
    nr = 0;
    for(i=n; i; --i)
    {
        while(nr && a[st[nr]] < a[i]) --nr;
        if(nr) add_edge(i, st[nr]);
        st[++nr] = i;
    }

    while(q--)
    {
        int x, y;
        cin >> x >> y;
        cout << dijkstra(x, y) - 1 << '\n';
    }
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n >> k >> q;
    for(i=1; i<=n; ++i) cin >> a[i];

    if(q <= 50) brute();
      //  else if(k<=20) solve0();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 4 ms 3008 KB Output is correct
5 Correct 4 ms 3068 KB Output is correct
6 Correct 4 ms 3068 KB Output is correct
7 Correct 4 ms 3068 KB Output is correct
8 Correct 4 ms 3068 KB Output is correct
9 Correct 4 ms 3068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3068 KB Output is correct
2 Correct 191 ms 8392 KB Output is correct
3 Correct 186 ms 8664 KB Output is correct
4 Correct 199 ms 8936 KB Output is correct
5 Correct 239 ms 9232 KB Output is correct
6 Correct 210 ms 9648 KB Output is correct
7 Correct 206 ms 10288 KB Output is correct
8 Correct 76 ms 10288 KB Output is correct
9 Correct 77 ms 10948 KB Output is correct
10 Correct 79 ms 11152 KB Output is correct
11 Correct 181 ms 12064 KB Output is correct
12 Correct 183 ms 12652 KB Output is correct
13 Correct 188 ms 13348 KB Output is correct
14 Correct 177 ms 13804 KB Output is correct
15 Correct 185 ms 14340 KB Output is correct
16 Correct 170 ms 14852 KB Output is correct
17 Correct 221 ms 15656 KB Output is correct
18 Correct 202 ms 16116 KB Output is correct
19 Correct 131 ms 16192 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 16192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 16192 KB Output isn't correct
2 Halted 0 ms 0 KB -