oj.uz

Submission #873109

# Submission time Handle Problem Language Result Execution time Memory
873109 2023-11-14T13:16:36 Z boris_mihov Passport (JOI23_passport) C++17
6 / 100
 526 ms 330284 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);
        assert(cnt < 2 * n);
    }

    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 132 ms 288336 KB Output is correct
2 Correct 141 ms 288416 KB Output is correct
3 Correct 130 ms 288304 KB Output is correct
4 Correct 526 ms 330284 KB Output is correct
5 Correct 292 ms 310100 KB Output is correct
6 Correct 236 ms 305108 KB Output is correct
7 Correct 199 ms 303116 KB Output is correct
8 Correct 212 ms 310580 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 288540 KB Output is correct
2 Correct 154 ms 288496 KB Output is correct
3 Correct 134 ms 288432 KB Output is correct
4 Correct 140 ms 288764 KB Output is correct
5 Correct 131 ms 288540 KB Output is correct
6 Correct 129 ms 288516 KB Output is correct
7 Correct 131 ms 288336 KB Output is correct
8 Incorrect 138 ms 288476 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 288540 KB Output is correct
2 Correct 154 ms 288496 KB Output is correct
3 Correct 134 ms 288432 KB Output is correct
4 Correct 140 ms 288764 KB Output is correct
5 Correct 131 ms 288540 KB Output is correct
6 Correct 129 ms 288516 KB Output is correct
7 Correct 131 ms 288336 KB Output is correct
8 Incorrect 138 ms 288476 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 288540 KB Output is correct
2 Correct 154 ms 288496 KB Output is correct
3 Correct 134 ms 288432 KB Output is correct
4 Correct 140 ms 288764 KB Output is correct
5 Correct 131 ms 288540 KB Output is correct
6 Correct 129 ms 288516 KB Output is correct
7 Correct 131 ms 288336 KB Output is correct
8 Incorrect 138 ms 288476 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 288336 KB Output is correct
2 Correct 141 ms 288416 KB Output is correct
3 Correct 130 ms 288304 KB Output is correct
4 Correct 526 ms 330284 KB Output is correct
5 Correct 292 ms 310100 KB Output is correct
6 Correct 236 ms 305108 KB Output is correct
7 Correct 199 ms 303116 KB Output is correct
8 Correct 212 ms 310580 KB Output is correct
9 Correct 132 ms 288540 KB Output is correct
10 Correct 154 ms 288496 KB Output is correct
11 Correct 134 ms 288432 KB Output is correct
12 Correct 140 ms 288764 KB Output is correct
13 Correct 131 ms 288540 KB Output is correct
14 Correct 129 ms 288516 KB Output is correct
15 Correct 131 ms 288336 KB Output is correct
16 Incorrect 138 ms 288476 KB Output isn't correct
17 Halted 0 ms 0 KB -