oj.uz

Submission #873100

# Submission time Handle Problem Language Result Execution time Memory
873100 2023-11-14T12:54:57 Z boris_mihov Passport (JOI23_passport) C++17
48 / 100
 2000 ms 1048576 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

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

int n;
int queries;
int l[MAXN];
int r[MAXN];
int dist[MAXN];
int distA[MAXN];
int distB[MAXN];
std::vector <int> g[MAXN];
std::queue <int> q[2 * MAXN];
std::queue <int> bfsQueue;
bool vis[MAXN];

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = l[i] ; j <= r[i] ; ++j)
        {
            // std::cout << "edge: " << i << ' ' << j << '\n';
            g[j].push_back(i);
        }
    }

    std::fill(distA + 1, distA + 1 + n, INF);
    std::fill(distB + 1, distB + 1 + n, INF);
    bfsQueue.push(1);
    distA[1] = 0;

    while (!bfsQueue.empty())
    {
        int top = bfsQueue.front();
        bfsQueue.pop();

        for (const int &u : g[top])
        {
            if (distA[u] > distA[top] + 1)
            {
                distA[u] = distA[top] + 1;
                bfsQueue.push(u);
            }
        }   
    }

    bfsQueue.push(n);
    distB[n] = 0;

    while (!bfsQueue.empty())
    {
        int top = bfsQueue.front();
        bfsQueue.pop();

        for (const int &u : g[top])
        {
            if (distB[u] > distB[top] + 1)
            {
                distB[u] = distB[top] + 1;
                bfsQueue.push(u);
            }
        }   
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        dist[i] = distA[i] + distB[i] - (distA[i] > 0 && distB[i] > 0);
        if (dist[i] <= 2 * n) q[dist[i]].push(i);
    }

    for (int d = 0 ; d <= n ; ++d)
    {
        while (!q[d].empty())
        {
            int top = q[d].front();
            q[d].pop();

            if (vis[top])
            {
                continue;
            }

            vis[top] = true;
            for (const int &u : g[top])
            {
                if (dist[u] > dist[top] + 1)
                {
                    dist[u] = dist[top] + 1;
                    q[dist[u]].push(u);
                }
            }
        }
    }

    for (int i = 1 ; i <= queries ; ++i)
    {
        int node;
        std::cin >> node;
        if (dist[node] <= n) std::cout << dist[node] << '\n';
        else std::cout << -1 << '\n';
    }
}

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

    std::cin >> queries;
}

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 146 ms 277328 KB Output is correct
2 Correct 121 ms 277328 KB Output is correct
3 Correct 136 ms 277332 KB Output is correct
4 Execution timed out 2012 ms 1048576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 277336 KB Output is correct
2 Correct 138 ms 277220 KB Output is correct
3 Correct 134 ms 277176 KB Output is correct
4 Correct 136 ms 277328 KB Output is correct
5 Correct 145 ms 277204 KB Output is correct
6 Correct 162 ms 277520 KB Output is correct
7 Correct 141 ms 277356 KB Output is correct
8 Correct 138 ms 277408 KB Output is correct
9 Correct 161 ms 277212 KB Output is correct
10 Correct 136 ms 277224 KB Output is correct
11 Correct 157 ms 277548 KB Output is correct
12 Correct 137 ms 277232 KB Output is correct
13 Correct 161 ms 277708 KB Output is correct
14 Correct 159 ms 277588 KB Output is correct
15 Correct 136 ms 277396 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 277336 KB Output is correct
2 Correct 138 ms 277220 KB Output is correct
3 Correct 134 ms 277176 KB Output is correct
4 Correct 136 ms 277328 KB Output is correct
5 Correct 145 ms 277204 KB Output is correct
6 Correct 162 ms 277520 KB Output is correct
7 Correct 141 ms 277356 KB Output is correct
8 Correct 138 ms 277408 KB Output is correct
9 Correct 161 ms 277212 KB Output is correct
10 Correct 136 ms 277224 KB Output is correct
11 Correct 157 ms 277548 KB Output is correct
12 Correct 137 ms 277232 KB Output is correct
13 Correct 161 ms 277708 KB Output is correct
14 Correct 159 ms 277588 KB Output is correct
15 Correct 136 ms 277396 KB Output is correct
16 Correct 178 ms 285712 KB Output is correct
17 Correct 173 ms 277460 KB Output is correct
18 Correct 180 ms 294592 KB Output is correct
19 Correct 175 ms 293452 KB Output is correct
20 Correct 150 ms 277424 KB Output is correct
21 Correct 156 ms 279780 KB Output is correct
22 Correct 176 ms 297372 KB Output is correct
23 Correct 182 ms 291552 KB Output is correct
24 Correct 187 ms 292384 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 277336 KB Output is correct
2 Correct 138 ms 277220 KB Output is correct
3 Correct 134 ms 277176 KB Output is correct
4 Correct 136 ms 277328 KB Output is correct
5 Correct 145 ms 277204 KB Output is correct
6 Correct 162 ms 277520 KB Output is correct
7 Correct 141 ms 277356 KB Output is correct
8 Correct 138 ms 277408 KB Output is correct
9 Correct 161 ms 277212 KB Output is correct
10 Correct 136 ms 277224 KB Output is correct
11 Correct 157 ms 277548 KB Output is correct
12 Correct 137 ms 277232 KB Output is correct
13 Correct 161 ms 277708 KB Output is correct
14 Correct 159 ms 277588 KB Output is correct
15 Correct 136 ms 277396 KB Output is correct
16 Correct 178 ms 285712 KB Output is correct
17 Correct 173 ms 277460 KB Output is correct
18 Correct 180 ms 294592 KB Output is correct
19 Correct 175 ms 293452 KB Output is correct
20 Correct 150 ms 277424 KB Output is correct
21 Correct 156 ms 279780 KB Output is correct
22 Correct 176 ms 297372 KB Output is correct
23 Correct 182 ms 291552 KB Output is correct
24 Correct 187 ms 292384 KB Output is correct
25 Correct 136 ms 277328 KB Output is correct
26 Correct 141 ms 277168 KB Output is correct
27 Correct 173 ms 286220 KB Output is correct
28 Correct 137 ms 277464 KB Output is correct
29 Correct 149 ms 277560 KB Output is correct
30 Correct 159 ms 279504 KB Output is correct
31 Correct 163 ms 287504 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 277328 KB Output is correct
2 Correct 121 ms 277328 KB Output is correct
3 Correct 136 ms 277332 KB Output is correct
4 Execution timed out 2012 ms 1048576 KB Time limit exceeded
5 Halted 0 ms 0 KB -