제출 #90385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90385		Alexa2001	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	618 ms	67644 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5, Kmax = 22;

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

int goL[Nmax][Kmax], goR[Nmax][Kmax], L[Nmax][Kmax], R[Nmax][Kmax], cnt[Kmax][Nmax];

int cate(int tip, int x, int y)
{
    return cnt[tip][y] - cnt[tip][x-1];
}

int walk(int x, int y)
{
    if(x > y) swap(x, y);
    int train = min(a[x], a[y]);
    return cate(train, x+1, y);
}

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

void solve0()
{
    int i, j, t;

    /// sume partiale
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=k; ++j)
            cnt[j][i] = cnt[j][i-1];
        for(j=a[i]; j; --j) cnt[j][i]++;
    }

    /// primul la stanga cu valuarea >= j
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=k; ++j)
            L[i][j] = L[i-1][j];
        for(j=a[i]; j; --j) L[i][j] = i;
    }

    /// primul la dreapta cu valuarea >= j
    for(i=n; i; --i)
    {
        for(j=1; j<=k; ++j)
            R[i][j] = R[i+1][j];
        for(j=a[i]; j; --j) R[i][j] = i;
    }

    /// cati pasi imi ia sa ajung in L[i][j] / R[i][j]

    for(i=1; i<=k; ++i)
    {
        for(j=1; j<=n; ++j)
        {
            goL[j][i] = goR[j][i] = n+5;

            if(a[j] >= i) goL[j][i] = goR[j][i] = 0;
                else
                {
                    for(t=1; t < i; ++t)
                    {
                        goL[j][i] = min(goL[j][i], walk(L[j][i], L[j][t]) + goL[j][t]);
                        goL[j][i] = min(goL[j][i], walk(L[j][i], R[j][t]) + goR[j][t]);
                    }

                    for(t=1; t < i; ++t)
                    {
                        goR[j][i] = min(goR[j][i], walk(R[j][i], L[j][t]) + goL[j][t]);
                        goR[j][i] = min(goR[j][i], walk(R[j][i], R[j][t]) + goR[j][t]);
                    }
                }
        }
    }

    while(q--)
    {
        int x, y;
        cin >> x >> y;

        int ans = n + 5;
        for(t=1; t<=k; ++t)
        {
            int v1, v2, v3, v4;

            v1 = goL[x][t] + goL[y][t] + walk(L[x][t], L[y][t]);
            v2 = goL[x][t] + goR[y][t] + walk(L[x][t], R[y][t]);
            v3 = goR[x][t] + goL[y][t] + walk(R[x][t], L[y][t]);
            v4 = goR[x][t] + goR[y][t] + walk(R[x][t], R[y][t]);

            ans = min(ans, v1);
            ans = min(ans, v2);
            ans = min(ans, v3);
            ans = min(ans, v4);
        }
        cout << ans - 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: 25 / 25
• Subtask 4: 0 / 55