Submission #90376

#	Time	Username	Problem	Language	Result	Execution time	Memory
90376		Alexa2001	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	239 ms	16192 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55