oj.uz

Submission #90385

# Submission time Handle Problem Language Result Execution time Memory
90385 2018-12-21T12:50:13 Z Alexa2001 Railway Trip (JOI17_railway_trip) C++17
45 / 100
 618 ms 67644 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2804 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 4 ms 2932 KB Output is correct
6 Correct 4 ms 2932 KB Output is correct
7 Correct 4 ms 2932 KB Output is correct
8 Correct 3 ms 2932 KB Output is correct
9 Correct 3 ms 2932 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3024 KB Output is correct
2 Correct 174 ms 8016 KB Output is correct
3 Correct 181 ms 8020 KB Output is correct
4 Correct 176 ms 8020 KB Output is correct
5 Correct 189 ms 8060 KB Output is correct
6 Correct 214 ms 8136 KB Output is correct
7 Correct 209 ms 8300 KB Output is correct
8 Correct 74 ms 8300 KB Output is correct
9 Correct 84 ms 8300 KB Output is correct
10 Correct 74 ms 8300 KB Output is correct
11 Correct 170 ms 8300 KB Output is correct
12 Correct 179 ms 8300 KB Output is correct
13 Correct 175 ms 8300 KB Output is correct
14 Correct 188 ms 8300 KB Output is correct
15 Correct 174 ms 8300 KB Output is correct
16 Correct 193 ms 8300 KB Output is correct
17 Correct 198 ms 8300 KB Output is correct
18 Correct 245 ms 8316 KB Output is correct
19 Correct 114 ms 8316 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 44796 KB Output is correct
2 Correct 361 ms 44796 KB Output is correct
3 Correct 452 ms 47952 KB Output is correct
4 Correct 500 ms 49740 KB Output is correct
5 Correct 551 ms 51532 KB Output is correct
6 Correct 559 ms 53708 KB Output is correct
7 Correct 589 ms 55644 KB Output is correct
8 Correct 250 ms 55644 KB Output is correct
9 Correct 405 ms 56484 KB Output is correct
10 Correct 483 ms 59652 KB Output is correct
11 Correct 507 ms 61100 KB Output is correct
12 Correct 531 ms 62432 KB Output is correct
13 Correct 506 ms 63844 KB Output is correct
14 Correct 520 ms 65076 KB Output is correct
15 Correct 618 ms 66404 KB Output is correct
16 Correct 616 ms 67644 KB Output is correct

Subtask #4
0 / 55.0

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