Submission #70043

#	Time	Username	Problem	Language	Result	Execution time	Memory
70043		antimirage	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2071 ms	17204 KiB

railway_trip

#include <algorithm>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include <queue>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

int n, k, q, ar[N], u[N], a, b, used[N], v;

vector <int> g[N];

queue <int> qu;

main()
{
    cin >> n >> k >> q;

    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]);

    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            if (ar[j] >= ar[i])
            {
                g[i].pb(j);
                break;
            }
        }
        for (int j = i + 1; j <= n; j++)
        {
            if (ar[j] >= ar[i])
            {
                g[i].pb(j);
                break;
            }
        }
    }
    while (q--)
    {
        memset(u, -1, sizeof(u));
        memset(used, -1, sizeof(used));
        scanf("%d%d", &a, &b);

        v = a;

        qu.push(v);
        u[v] = 0;

        while (!qu.empty())
        {
            v = qu.front();
            qu.pop();
            for(auto to : g[v])
            {
                if ( u[to] == -1 )
                {
                    qu.push(to);
                    u[to] = u[v] + 1;
                }
            }
        }
        int ans = (u[b] == -1 ? 1e9 + 7 : u[b] - 1);

        v = b;

        qu.push(v);
        used[v] = 0;

        while (!qu.empty())
        {
            v = qu.front();
            qu.pop();
            for(auto to : g[v])
            {
                if ( used[to] == -1 )
                {
                    qu.push(to);
                    used[to] = used[v] + 1;
                }
            }
        }
        ans = (used[a] == -1 ? ans : used[a] - 1);

        for (int i = 1; i <= n; i++)
        {
            if (used[i] != -1 && u[i] != -1)
                ans = min(ans, used[i] + u[i] - 1);
        }
        printf("%d\n", ans);
    }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
         ~~~~~^~~~~~~~~~~~~~
railway_trip.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

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