oj.uz

Submission #855146

# Submission time Handle Problem Language Result Execution time Memory
855146 2023-09-30T10:08:46 Z boris_mihov Passport (JOI23_passport) C++17
48 / 100
 622 ms 669012 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 2500 + 10;
const int INF  = 1e9;

int n, q;
int l[MAXN];
int r[MAXN];
int dist[MAXN * MAXN];
bool vis[MAXN * MAXN];

int encode(int l, int r)
{
    return (l - 1) * n + r;
}

std::vector <std::pair <int,int>> g[MAXN * MAXN];
std::deque <int> dq;
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        int maxR = 0;
        int minL = n + 1;
        for (int j = i ; j <= n ; ++j)
        {
            maxR = std::max(maxR, r[j]);
            minL = std::min(minL, l[j]);
            g[encode(minL, j)].push_back({encode(i, j), 1});
            g[encode(i, maxR)].push_back({encode(i, j), 1});
            g[encode(l[i], r[i])].push_back({encode(i, j), 1});
            if (i != j) g[encode(i + 1, j)].push_back({encode(i, j), 0});
        }
    }

    std::fill(dist, dist + MAXN * MAXN, INF);
    dq.push_back(encode(1, n));
    dist[encode(1, n)] = 0;

    while (!dq.empty())
    {
        int top = dq.front();
        dq.pop_front();

        if (vis[top]) continue;
        vis[top] = true;

        for (const auto &[u, d] : g[top])
        {
            if (d == 0 && dist[u] > dist[top])
            {
                dist[u] = dist[top];
                dq.push_front(u);
            }

            if (d == 1 && dist[u] > dist[top] + d)
            {
                dist[u] = dist[top] + d;
                dq.push_back(u);
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (dist[encode(i, i)] == INF)
        {
            dist[encode(i, i)] = -1;
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        int idx;
        std::cin >> idx;
        std::cout << dist[encode(idx, idx)] << '\n';
    }
}  

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }

    std::cin >> q;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 175036 KB Output is correct
2 Correct 36 ms 174932 KB Output is correct
3 Correct 40 ms 174932 KB Output is correct
4 Runtime error 494 ms 669012 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 174956 KB Output is correct
2 Correct 37 ms 174940 KB Output is correct
3 Correct 36 ms 174932 KB Output is correct
4 Correct 36 ms 174932 KB Output is correct
5 Correct 36 ms 174940 KB Output is correct
6 Correct 36 ms 174940 KB Output is correct
7 Correct 37 ms 175196 KB Output is correct
8 Correct 35 ms 174932 KB Output is correct
9 Correct 36 ms 174940 KB Output is correct
10 Correct 36 ms 174932 KB Output is correct
11 Correct 42 ms 177756 KB Output is correct
12 Correct 44 ms 177756 KB Output is correct
13 Correct 42 ms 177916 KB Output is correct
14 Correct 41 ms 177864 KB Output is correct
15 Correct 43 ms 177492 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 174956 KB Output is correct
2 Correct 37 ms 174940 KB Output is correct
3 Correct 36 ms 174932 KB Output is correct
4 Correct 36 ms 174932 KB Output is correct
5 Correct 36 ms 174940 KB Output is correct
6 Correct 36 ms 174940 KB Output is correct
7 Correct 37 ms 175196 KB Output is correct
8 Correct 35 ms 174932 KB Output is correct
9 Correct 36 ms 174940 KB Output is correct
10 Correct 36 ms 174932 KB Output is correct
11 Correct 42 ms 177756 KB Output is correct
12 Correct 44 ms 177756 KB Output is correct
13 Correct 42 ms 177916 KB Output is correct
14 Correct 41 ms 177864 KB Output is correct
15 Correct 43 ms 177492 KB Output is correct
16 Correct 400 ms 358700 KB Output is correct
17 Correct 620 ms 359260 KB Output is correct
18 Correct 457 ms 368472 KB Output is correct
19 Correct 405 ms 367108 KB Output is correct
20 Correct 528 ms 357204 KB Output is correct
21 Correct 437 ms 346456 KB Output is correct
22 Correct 378 ms 377968 KB Output is correct
23 Correct 429 ms 381312 KB Output is correct
24 Correct 447 ms 380812 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 174956 KB Output is correct
2 Correct 37 ms 174940 KB Output is correct
3 Correct 36 ms 174932 KB Output is correct
4 Correct 36 ms 174932 KB Output is correct
5 Correct 36 ms 174940 KB Output is correct
6 Correct 36 ms 174940 KB Output is correct
7 Correct 37 ms 175196 KB Output is correct
8 Correct 35 ms 174932 KB Output is correct
9 Correct 36 ms 174940 KB Output is correct
10 Correct 36 ms 174932 KB Output is correct
11 Correct 42 ms 177756 KB Output is correct
12 Correct 44 ms 177756 KB Output is correct
13 Correct 42 ms 177916 KB Output is correct
14 Correct 41 ms 177864 KB Output is correct
15 Correct 43 ms 177492 KB Output is correct
16 Correct 400 ms 358700 KB Output is correct
17 Correct 620 ms 359260 KB Output is correct
18 Correct 457 ms 368472 KB Output is correct
19 Correct 405 ms 367108 KB Output is correct
20 Correct 528 ms 357204 KB Output is correct
21 Correct 437 ms 346456 KB Output is correct
22 Correct 378 ms 377968 KB Output is correct
23 Correct 429 ms 381312 KB Output is correct
24 Correct 447 ms 380812 KB Output is correct
25 Correct 36 ms 174932 KB Output is correct
26 Correct 36 ms 175104 KB Output is correct
27 Correct 405 ms 371756 KB Output is correct
28 Correct 622 ms 361836 KB Output is correct
29 Correct 513 ms 356624 KB Output is correct
30 Correct 426 ms 346992 KB Output is correct
31 Correct 402 ms 369888 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 175036 KB Output is correct
2 Correct 36 ms 174932 KB Output is correct
3 Correct 40 ms 174932 KB Output is correct
4 Runtime error 494 ms 669012 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -