oj.uz

Submission #873002

# Submission time Handle Problem Language Result Execution time Memory
873002 2023-11-14T09:29:31 Z boris_mihov Passport (JOI23_passport) C++17
0 / 100
 1972 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::vector <int> rev[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[i].push_back(j);
            rev[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 : rev[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 : rev[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];
        if (l[i] == 1 && r[i] == n) dist[i] = 1;
        if (dist[i] <= 2 * n) q[dist[i]].push(i);
    }

    for (int d = 0 ; d <= 2 * 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 : rev[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] < 2 * 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 182 ms 279356 KB Output is correct
2 Correct 145 ms 279000 KB Output is correct
3 Correct 145 ms 278920 KB Output is correct
4 Runtime error 1972 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 279648 KB Output is correct
2 Correct 145 ms 281532 KB Output is correct
3 Correct 142 ms 281512 KB Output is correct
4 Correct 143 ms 281356 KB Output is correct
5 Correct 140 ms 281424 KB Output is correct
6 Correct 144 ms 281516 KB Output is correct
7 Correct 141 ms 281424 KB Output is correct
8 Incorrect 142 ms 281320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 279648 KB Output is correct
2 Correct 145 ms 281532 KB Output is correct
3 Correct 142 ms 281512 KB Output is correct
4 Correct 143 ms 281356 KB Output is correct
5 Correct 140 ms 281424 KB Output is correct
6 Correct 144 ms 281516 KB Output is correct
7 Correct 141 ms 281424 KB Output is correct
8 Incorrect 142 ms 281320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 279648 KB Output is correct
2 Correct 145 ms 281532 KB Output is correct
3 Correct 142 ms 281512 KB Output is correct
4 Correct 143 ms 281356 KB Output is correct
5 Correct 140 ms 281424 KB Output is correct
6 Correct 144 ms 281516 KB Output is correct
7 Correct 141 ms 281424 KB Output is correct
8 Incorrect 142 ms 281320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 279356 KB Output is correct
2 Correct 145 ms 279000 KB Output is correct
3 Correct 145 ms 278920 KB Output is correct
4 Runtime error 1972 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -