oj.uz

Submission #873115

# Submission time Handle Problem Language Result Execution time Memory
873115 2023-11-14T13:25:09 Z boris_mihov Passport (JOI23_passport) C++17
100 / 100
 742 ms 628360 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 400000 + 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);
    }

    std::fill(dist + n + 1, dist + tree.cnt + 1, INF);
    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 282 ms 568400 KB Output is correct
2 Correct 255 ms 568404 KB Output is correct
3 Correct 258 ms 568588 KB Output is correct
4 Correct 684 ms 616812 KB Output is correct
5 Correct 458 ms 596524 KB Output is correct
6 Correct 386 ms 591448 KB Output is correct
7 Correct 347 ms 589452 KB Output is correct
8 Correct 384 ms 596816 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 568492 KB Output is correct
2 Correct 252 ms 568404 KB Output is correct
3 Correct 262 ms 568516 KB Output is correct
4 Correct 270 ms 568508 KB Output is correct
5 Correct 260 ms 568576 KB Output is correct
6 Correct 254 ms 568572 KB Output is correct
7 Correct 255 ms 568492 KB Output is correct
8 Correct 255 ms 568428 KB Output is correct
9 Correct 266 ms 568556 KB Output is correct
10 Correct 280 ms 568652 KB Output is correct
11 Correct 253 ms 568628 KB Output is correct
12 Correct 284 ms 568660 KB Output is correct
13 Correct 287 ms 568420 KB Output is correct
14 Correct 256 ms 568400 KB Output is correct
15 Correct 270 ms 568664 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 568492 KB Output is correct
2 Correct 252 ms 568404 KB Output is correct
3 Correct 262 ms 568516 KB Output is correct
4 Correct 270 ms 568508 KB Output is correct
5 Correct 260 ms 568576 KB Output is correct
6 Correct 254 ms 568572 KB Output is correct
7 Correct 255 ms 568492 KB Output is correct
8 Correct 255 ms 568428 KB Output is correct
9 Correct 266 ms 568556 KB Output is correct
10 Correct 280 ms 568652 KB Output is correct
11 Correct 253 ms 568628 KB Output is correct
12 Correct 284 ms 568660 KB Output is correct
13 Correct 287 ms 568420 KB Output is correct
14 Correct 256 ms 568400 KB Output is correct
15 Correct 270 ms 568664 KB Output is correct
16 Correct 288 ms 568912 KB Output is correct
17 Correct 301 ms 568644 KB Output is correct
18 Correct 268 ms 569200 KB Output is correct
19 Correct 259 ms 568884 KB Output is correct
20 Correct 260 ms 568812 KB Output is correct
21 Correct 255 ms 568736 KB Output is correct
22 Correct 291 ms 568624 KB Output is correct
23 Correct 304 ms 568892 KB Output is correct
24 Correct 274 ms 568728 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 568492 KB Output is correct
2 Correct 252 ms 568404 KB Output is correct
3 Correct 262 ms 568516 KB Output is correct
4 Correct 270 ms 568508 KB Output is correct
5 Correct 260 ms 568576 KB Output is correct
6 Correct 254 ms 568572 KB Output is correct
7 Correct 255 ms 568492 KB Output is correct
8 Correct 255 ms 568428 KB Output is correct
9 Correct 266 ms 568556 KB Output is correct
10 Correct 280 ms 568652 KB Output is correct
11 Correct 253 ms 568628 KB Output is correct
12 Correct 284 ms 568660 KB Output is correct
13 Correct 287 ms 568420 KB Output is correct
14 Correct 256 ms 568400 KB Output is correct
15 Correct 270 ms 568664 KB Output is correct
16 Correct 288 ms 568912 KB Output is correct
17 Correct 301 ms 568644 KB Output is correct
18 Correct 268 ms 569200 KB Output is correct
19 Correct 259 ms 568884 KB Output is correct
20 Correct 260 ms 568812 KB Output is correct
21 Correct 255 ms 568736 KB Output is correct
22 Correct 291 ms 568624 KB Output is correct
23 Correct 304 ms 568892 KB Output is correct
24 Correct 274 ms 568728 KB Output is correct
25 Correct 265 ms 568656 KB Output is correct
26 Correct 249 ms 568524 KB Output is correct
27 Correct 257 ms 568916 KB Output is correct
28 Correct 268 ms 568820 KB Output is correct
29 Correct 257 ms 568660 KB Output is correct
30 Correct 261 ms 568796 KB Output is correct
31 Correct 273 ms 568608 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 568400 KB Output is correct
2 Correct 255 ms 568404 KB Output is correct
3 Correct 258 ms 568588 KB Output is correct
4 Correct 684 ms 616812 KB Output is correct
5 Correct 458 ms 596524 KB Output is correct
6 Correct 386 ms 591448 KB Output is correct
7 Correct 347 ms 589452 KB Output is correct
8 Correct 384 ms 596816 KB Output is correct
9 Correct 251 ms 568492 KB Output is correct
10 Correct 252 ms 568404 KB Output is correct
11 Correct 262 ms 568516 KB Output is correct
12 Correct 270 ms 568508 KB Output is correct
13 Correct 260 ms 568576 KB Output is correct
14 Correct 254 ms 568572 KB Output is correct
15 Correct 255 ms 568492 KB Output is correct
16 Correct 255 ms 568428 KB Output is correct
17 Correct 266 ms 568556 KB Output is correct
18 Correct 280 ms 568652 KB Output is correct
19 Correct 253 ms 568628 KB Output is correct
20 Correct 284 ms 568660 KB Output is correct
21 Correct 287 ms 568420 KB Output is correct
22 Correct 256 ms 568400 KB Output is correct
23 Correct 270 ms 568664 KB Output is correct
24 Correct 288 ms 568912 KB Output is correct
25 Correct 301 ms 568644 KB Output is correct
26 Correct 268 ms 569200 KB Output is correct
27 Correct 259 ms 568884 KB Output is correct
28 Correct 260 ms 568812 KB Output is correct
29 Correct 255 ms 568736 KB Output is correct
30 Correct 291 ms 568624 KB Output is correct
31 Correct 304 ms 568892 KB Output is correct
32 Correct 274 ms 568728 KB Output is correct
33 Correct 265 ms 568656 KB Output is correct
34 Correct 249 ms 568524 KB Output is correct
35 Correct 257 ms 568916 KB Output is correct
36 Correct 268 ms 568820 KB Output is correct
37 Correct 257 ms 568660 KB Output is correct
38 Correct 261 ms 568796 KB Output is correct
39 Correct 273 ms 568608 KB Output is correct
40 Correct 742 ms 617496 KB Output is correct
41 Correct 479 ms 601476 KB Output is correct
42 Correct 541 ms 628004 KB Output is correct
43 Correct 548 ms 628360 KB Output is correct
44 Correct 410 ms 596660 KB Output is correct
45 Correct 454 ms 602700 KB Output is correct
46 Correct 340 ms 580072 KB Output is correct
47 Correct 485 ms 603852 KB Output is correct
48 Correct 482 ms 610992 KB Output is correct