oj.uz

Submission #873111

# Submission time Handle Problem Language Result Execution time Memory
873111 2023-11-14T13:21:38 Z boris_mihov Passport (JOI23_passport) C++17
22 / 100
 503 ms 331476 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 <= tree.cnt ; ++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 149 ms 288388 KB Output is correct
2 Correct 129 ms 288340 KB Output is correct
3 Correct 130 ms 288416 KB Output is correct
4 Correct 503 ms 331476 KB Output is correct
5 Correct 285 ms 311124 KB Output is correct
6 Correct 236 ms 305904 KB Output is correct
7 Correct 203 ms 303872 KB Output is correct
8 Correct 213 ms 310556 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 288336 KB Output is correct
2 Correct 129 ms 288372 KB Output is correct
3 Correct 129 ms 288340 KB Output is correct
4 Correct 127 ms 288500 KB Output is correct
5 Correct 132 ms 288416 KB Output is correct
6 Correct 130 ms 288332 KB Output is correct
7 Correct 138 ms 288448 KB Output is correct
8 Correct 129 ms 288400 KB Output is correct
9 Correct 135 ms 288536 KB Output is correct
10 Correct 136 ms 288540 KB Output is correct
11 Correct 128 ms 288472 KB Output is correct
12 Correct 145 ms 288384 KB Output is correct
13 Correct 144 ms 288596 KB Output is correct
14 Correct 147 ms 288592 KB Output is correct
15 Correct 132 ms 288564 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 288336 KB Output is correct
2 Correct 129 ms 288372 KB Output is correct
3 Correct 129 ms 288340 KB Output is correct
4 Correct 127 ms 288500 KB Output is correct
5 Correct 132 ms 288416 KB Output is correct
6 Correct 130 ms 288332 KB Output is correct
7 Correct 138 ms 288448 KB Output is correct
8 Correct 129 ms 288400 KB Output is correct
9 Correct 135 ms 288536 KB Output is correct
10 Correct 136 ms 288540 KB Output is correct
11 Correct 128 ms 288472 KB Output is correct
12 Correct 145 ms 288384 KB Output is correct
13 Correct 144 ms 288596 KB Output is correct
14 Correct 147 ms 288592 KB Output is correct
15 Correct 132 ms 288564 KB Output is correct
16 Incorrect 136 ms 288800 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 288336 KB Output is correct
2 Correct 129 ms 288372 KB Output is correct
3 Correct 129 ms 288340 KB Output is correct
4 Correct 127 ms 288500 KB Output is correct
5 Correct 132 ms 288416 KB Output is correct
6 Correct 130 ms 288332 KB Output is correct
7 Correct 138 ms 288448 KB Output is correct
8 Correct 129 ms 288400 KB Output is correct
9 Correct 135 ms 288536 KB Output is correct
10 Correct 136 ms 288540 KB Output is correct
11 Correct 128 ms 288472 KB Output is correct
12 Correct 145 ms 288384 KB Output is correct
13 Correct 144 ms 288596 KB Output is correct
14 Correct 147 ms 288592 KB Output is correct
15 Correct 132 ms 288564 KB Output is correct
16 Incorrect 136 ms 288800 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 288388 KB Output is correct
2 Correct 129 ms 288340 KB Output is correct
3 Correct 130 ms 288416 KB Output is correct
4 Correct 503 ms 331476 KB Output is correct
5 Correct 285 ms 311124 KB Output is correct
6 Correct 236 ms 305904 KB Output is correct
7 Correct 203 ms 303872 KB Output is correct
8 Correct 213 ms 310556 KB Output is correct
9 Correct 128 ms 288336 KB Output is correct
10 Correct 129 ms 288372 KB Output is correct
11 Correct 129 ms 288340 KB Output is correct
12 Correct 127 ms 288500 KB Output is correct
13 Correct 132 ms 288416 KB Output is correct
14 Correct 130 ms 288332 KB Output is correct
15 Correct 138 ms 288448 KB Output is correct
16 Correct 129 ms 288400 KB Output is correct
17 Correct 135 ms 288536 KB Output is correct
18 Correct 136 ms 288540 KB Output is correct
19 Correct 128 ms 288472 KB Output is correct
20 Correct 145 ms 288384 KB Output is correct
21 Correct 144 ms 288596 KB Output is correct
22 Correct 147 ms 288592 KB Output is correct
23 Correct 132 ms 288564 KB Output is correct
24 Incorrect 136 ms 288800 KB Output isn't correct
25 Halted 0 ms 0 KB -