oj.uz

Submission #873108

# Submission time Handle Problem Language Result Execution time Memory
873108 2023-11-14T13:12:50 Z boris_mihov Passport (JOI23_passport) C++17
6 / 100
 488 ms 330420 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;
std::vector <std::pair <int,int>> g[2 * MAXN];
struct SegmentTree
{
    int cnt;
    int tree[4*MAXN];

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node] = l;
            return;
        }

        tree[node] = ++cnt;
        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        g[tree[2 * node]].push_back({tree[node], 0});
        g[tree[2 * node + 1]].push_back({tree[node], 0});
    }

    void addEdges(int l, int r, int node, int queryL, int queryR, int queryNode)
    {
        if (queryL <= l && r <= queryR)
        {
            g[tree[node]].push_back({queryNode, 1});
            return;
        }

        int mid = (l + r) / 2;
        if (queryL <= mid) addEdges(l, mid, 2*node, queryL, queryR, queryNode);
        if (mid + 1 <= queryR) addEdges(mid + 1, r, 2*node + 1, queryL, queryR, queryNode);
    }

    void build()
    {
        cnt = n;
        build(1, n, 1);
    }

    void addEdges(int to, int l, int r)
    {
        addEdges(1, n, 1, l, r, to);
    }
};

int queries;
int l[MAXN];
int r[MAXN];
int dist[2 * MAXN];
int distA[2 * MAXN];
int distB[2 * MAXN];
std::queue <int> q[2 * MAXN];
std::deque <int> dq;
SegmentTree tree;
bool vis[MAXN];

void solve()
{
    tree.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        tree.addEdges(i, l[i], r[i]);
    }   

    std::fill(distA + 1, distA + 1 + tree.cnt, INF);
    std::fill(distB + 1, distB + 1 + tree.cnt, INF);
    dq.push_back(1);
    distA[1] = 0;

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

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

    dq.push_back(n);
    distB[n] = 0;

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

        for (const auto &[u, d] : g[top])
        {
            if (distB[u] > distB[top] + d)
            {
                distB[u] = distB[top] + d;
                if (d == 0) dq.push_front(u);
                else dq.push_back(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 auto &[u, d] : g[top])
            {
                if (dist[u] > dist[top] + d)
                {
                    dist[u] = dist[top] + d;
                    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288336 KB Output is correct
2 Correct 139 ms 288688 KB Output is correct
3 Correct 131 ms 288344 KB Output is correct
4 Correct 488 ms 330420 KB Output is correct
5 Correct 286 ms 312808 KB Output is correct
6 Correct 228 ms 307528 KB Output is correct
7 Correct 201 ms 304864 KB Output is correct
8 Correct 216 ms 312224 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288500 KB Output is correct
2 Correct 128 ms 288368 KB Output is correct
3 Correct 132 ms 288592 KB Output is correct
4 Correct 130 ms 288420 KB Output is correct
5 Correct 128 ms 288336 KB Output is correct
6 Correct 128 ms 288500 KB Output is correct
7 Correct 135 ms 288596 KB Output is correct
8 Incorrect 158 ms 288340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288500 KB Output is correct
2 Correct 128 ms 288368 KB Output is correct
3 Correct 132 ms 288592 KB Output is correct
4 Correct 130 ms 288420 KB Output is correct
5 Correct 128 ms 288336 KB Output is correct
6 Correct 128 ms 288500 KB Output is correct
7 Correct 135 ms 288596 KB Output is correct
8 Incorrect 158 ms 288340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288500 KB Output is correct
2 Correct 128 ms 288368 KB Output is correct
3 Correct 132 ms 288592 KB Output is correct
4 Correct 130 ms 288420 KB Output is correct
5 Correct 128 ms 288336 KB Output is correct
6 Correct 128 ms 288500 KB Output is correct
7 Correct 135 ms 288596 KB Output is correct
8 Incorrect 158 ms 288340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 288336 KB Output is correct
2 Correct 139 ms 288688 KB Output is correct
3 Correct 131 ms 288344 KB Output is correct
4 Correct 488 ms 330420 KB Output is correct
5 Correct 286 ms 312808 KB Output is correct
6 Correct 228 ms 307528 KB Output is correct
7 Correct 201 ms 304864 KB Output is correct
8 Correct 216 ms 312224 KB Output is correct
9 Correct 129 ms 288500 KB Output is correct
10 Correct 128 ms 288368 KB Output is correct
11 Correct 132 ms 288592 KB Output is correct
12 Correct 130 ms 288420 KB Output is correct
13 Correct 128 ms 288336 KB Output is correct
14 Correct 128 ms 288500 KB Output is correct
15 Correct 135 ms 288596 KB Output is correct
16 Incorrect 158 ms 288340 KB Output isn't correct
17 Halted 0 ms 0 KB -