oj.uz

Submission #768731

# Submission time Handle Problem Language Result Execution time Memory
768731 2023-06-28T14:04:42 Z danikoynov Passport (JOI23_passport) C++14
100 / 100
 1331 ms 607780 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;


vector < pair < int, int > > adj[maxn * 2];
int dist[maxn * 2], lf[maxn * 2], rf[maxn * 2];
int fict, root, toi;


int build(int left, int right)
{
    ///cout << left << " :: " << right << " " << fict << endl;
    if (left == right)
        return left;
    int mid = (left + right) / 2;
    int left_child = build(left, mid);
    int right_child = build(mid + 1, right);
    int ver = ++ fict;
    adj[left_child].push_back({ver, 0});
    adj[right_child].push_back({ver, 0});
    //cout << left_child << " " << ver << " " << 0 << endl;
    //cout << right_child << " " << ver << " " << 0 << endl;
    lf[ver] = left_child;
    rf[ver] = right_child;
    return ver;
}
void graph(int _n)
{
    toi = _n;
    fict = _n;
    root = build(1, _n);

}

void range_update(int node, int l, int r, int ql, int qr, int v)
{
    if (l > qr || r < ql)
        return;

    if (l >= ql && r <= qr)
    {
        adj[node].push_back({v, 1});
        ///cout << "make edge " << node << " " << l << " " << r << " " << v << endl;
        ///cout << node << " " << v << " " << 1 << endl;
        return;
    }

    int m = (l + r) / 2;
    range_update(lf[node], l, m, ql, qr, v);
    range_update(rf[node], m + 1, r, ql, qr, v);
}
void add_range_edge(int l, int r, int v)
{
    range_update(root, 1, toi, l, r, v);
}
void add_edge(int v, int u, int w)
{
    adj[v].push_back({u, w});
    ///adj[u].push_back({v, w});
}
int used[4 * maxn];
struct edge
{
    int v, len;
    edge(int _v = 0, int _len = 0)
    {
        v = _v;
        len = _len;
    }
    bool operator < (const edge &e) const
    {
        return len > e.len;
    }
};

void bfs(int st, bool tf = false)
{
    for (int i = 1; i <= fict; i ++)
    {
        dist[i] = 1e9;
        used[i] = 0;
    }
 queue < int > qs[4 * maxn];

    qs[0].push(st);
    dist[st] = 0;

    for (int i = 0; i < 4 * maxn; i ++)
    while(!qs[i].empty())
    {
        int cur = qs[i].front();
        qs[i].pop();
        //cout << cur << " " << used[cur] << endl;
        if (used[cur])
            continue;
        used[cur] = 1;
        //if (tf)
          //  cout << "here " << v << " " << dist[v] << endl;
        for (pair < int, int > nb : adj[cur])
        {

            if (dist[nb.first] > dist[cur] + nb.second)
            {
                dist[nb.first] = dist[cur] + nb.second;
                qs[dist[cur] + nb.second].push(nb.first);
            }
        }
    }
}


int n, q, l[maxn], r[maxn];
int a[maxn], b[maxn];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }

    graph(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        add_range_edge(l[i], r[i], i);
        ///for (int j = l[i]; j <= r[i]; j ++)
        ///add_edge(j, i, 1);
        ///cout << j << " " << i << " " << 1 << endl;
    }

    bfs(1);
    for (int i = 1; i <= n; i ++)
        a[i] = dist[i];
    bfs(n);
    for (int i = 1; i <= n; i ++)
        b[i] = dist[i];

    /**for (int i = 1; i <= n; i ++)
        cout << b[i] << " ";
    cout << endl;
    return;*/
    ///cout << "------------" << endl;

    for (int i = 1; i <= n; i ++)
    {
        int edge = a[i] + b[i];
        if (a[i] > 0 && b[i] > 0)
            edge --;
        add_edge(n + 1, i, edge);
        ///cout << n + 1 << " " << i << " " << a[i] << " " << b[i] << endl;
    }

    bfs(n + 1, 1);
    /**for (int i = 1; i <= n; i ++)
        cout << dist[i] << " ";
    cout << endl;*/
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int x;
        cin >> x;
        int ans = dist[x];
        if (ans > n)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }



}

int main()
{
    speed();
    ///freopen("text.txt", "r", stdin);
    solve();
    return 0;
}
/**
9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 548320 KB Output is correct
2 Correct 635 ms 548412 KB Output is correct
3 Correct 593 ms 548324 KB Output is correct
4 Correct 1331 ms 599828 KB Output is correct
5 Correct 981 ms 579724 KB Output is correct
6 Correct 921 ms 574640 KB Output is correct
7 Correct 885 ms 596956 KB Output is correct
8 Correct 861 ms 589992 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 548320 KB Output is correct
2 Correct 639 ms 548368 KB Output is correct
3 Correct 622 ms 548316 KB Output is correct
4 Correct 643 ms 548308 KB Output is correct
5 Correct 616 ms 548320 KB Output is correct
6 Correct 668 ms 548220 KB Output is correct
7 Correct 663 ms 548316 KB Output is correct
8 Correct 614 ms 548324 KB Output is correct
9 Correct 631 ms 548320 KB Output is correct
10 Correct 673 ms 548260 KB Output is correct
11 Correct 753 ms 548504 KB Output is correct
12 Correct 867 ms 548484 KB Output is correct
13 Correct 820 ms 548392 KB Output is correct
14 Correct 742 ms 548424 KB Output is correct
15 Correct 738 ms 548368 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 548320 KB Output is correct
2 Correct 639 ms 548368 KB Output is correct
3 Correct 622 ms 548316 KB Output is correct
4 Correct 643 ms 548308 KB Output is correct
5 Correct 616 ms 548320 KB Output is correct
6 Correct 668 ms 548220 KB Output is correct
7 Correct 663 ms 548316 KB Output is correct
8 Correct 614 ms 548324 KB Output is correct
9 Correct 631 ms 548320 KB Output is correct
10 Correct 673 ms 548260 KB Output is correct
11 Correct 753 ms 548504 KB Output is correct
12 Correct 867 ms 548484 KB Output is correct
13 Correct 820 ms 548392 KB Output is correct
14 Correct 742 ms 548424 KB Output is correct
15 Correct 738 ms 548368 KB Output is correct
16 Correct 805 ms 548752 KB Output is correct
17 Correct 838 ms 548672 KB Output is correct
18 Correct 779 ms 549052 KB Output is correct
19 Correct 831 ms 548864 KB Output is correct
20 Correct 774 ms 548668 KB Output is correct
21 Correct 793 ms 548672 KB Output is correct
22 Correct 833 ms 549048 KB Output is correct
23 Correct 783 ms 548772 KB Output is correct
24 Correct 766 ms 548756 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 548320 KB Output is correct
2 Correct 639 ms 548368 KB Output is correct
3 Correct 622 ms 548316 KB Output is correct
4 Correct 643 ms 548308 KB Output is correct
5 Correct 616 ms 548320 KB Output is correct
6 Correct 668 ms 548220 KB Output is correct
7 Correct 663 ms 548316 KB Output is correct
8 Correct 614 ms 548324 KB Output is correct
9 Correct 631 ms 548320 KB Output is correct
10 Correct 673 ms 548260 KB Output is correct
11 Correct 753 ms 548504 KB Output is correct
12 Correct 867 ms 548484 KB Output is correct
13 Correct 820 ms 548392 KB Output is correct
14 Correct 742 ms 548424 KB Output is correct
15 Correct 738 ms 548368 KB Output is correct
16 Correct 805 ms 548752 KB Output is correct
17 Correct 838 ms 548672 KB Output is correct
18 Correct 779 ms 549052 KB Output is correct
19 Correct 831 ms 548864 KB Output is correct
20 Correct 774 ms 548668 KB Output is correct
21 Correct 793 ms 548672 KB Output is correct
22 Correct 833 ms 549048 KB Output is correct
23 Correct 783 ms 548772 KB Output is correct
24 Correct 766 ms 548756 KB Output is correct
25 Correct 609 ms 548460 KB Output is correct
26 Correct 636 ms 548328 KB Output is correct
27 Correct 736 ms 548952 KB Output is correct
28 Correct 753 ms 548684 KB Output is correct
29 Correct 798 ms 548620 KB Output is correct
30 Correct 705 ms 548664 KB Output is correct
31 Correct 802 ms 548904 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 548320 KB Output is correct
2 Correct 635 ms 548412 KB Output is correct
3 Correct 593 ms 548324 KB Output is correct
4 Correct 1331 ms 599828 KB Output is correct
5 Correct 981 ms 579724 KB Output is correct
6 Correct 921 ms 574640 KB Output is correct
7 Correct 885 ms 596956 KB Output is correct
8 Correct 861 ms 589992 KB Output is correct
9 Correct 634 ms 548320 KB Output is correct
10 Correct 639 ms 548368 KB Output is correct
11 Correct 622 ms 548316 KB Output is correct
12 Correct 643 ms 548308 KB Output is correct
13 Correct 616 ms 548320 KB Output is correct
14 Correct 668 ms 548220 KB Output is correct
15 Correct 663 ms 548316 KB Output is correct
16 Correct 614 ms 548324 KB Output is correct
17 Correct 631 ms 548320 KB Output is correct
18 Correct 673 ms 548260 KB Output is correct
19 Correct 753 ms 548504 KB Output is correct
20 Correct 867 ms 548484 KB Output is correct
21 Correct 820 ms 548392 KB Output is correct
22 Correct 742 ms 548424 KB Output is correct
23 Correct 738 ms 548368 KB Output is correct
24 Correct 805 ms 548752 KB Output is correct
25 Correct 838 ms 548672 KB Output is correct
26 Correct 779 ms 549052 KB Output is correct
27 Correct 831 ms 548864 KB Output is correct
28 Correct 774 ms 548668 KB Output is correct
29 Correct 793 ms 548672 KB Output is correct
30 Correct 833 ms 549048 KB Output is correct
31 Correct 783 ms 548772 KB Output is correct
32 Correct 766 ms 548756 KB Output is correct
33 Correct 609 ms 548460 KB Output is correct
34 Correct 636 ms 548328 KB Output is correct
35 Correct 736 ms 548952 KB Output is correct
36 Correct 753 ms 548684 KB Output is correct
37 Correct 798 ms 548620 KB Output is correct
38 Correct 705 ms 548664 KB Output is correct
39 Correct 802 ms 548904 KB Output is correct
40 Correct 1249 ms 600708 KB Output is correct
41 Correct 1004 ms 581068 KB Output is correct
42 Correct 1073 ms 607504 KB Output is correct
43 Correct 1073 ms 607780 KB Output is correct
44 Correct 908 ms 575324 KB Output is correct
45 Correct 1027 ms 582400 KB Output is correct
46 Correct 886 ms 562076 KB Output is correct
47 Correct 1027 ms 589956 KB Output is correct
48 Correct 1093 ms 590480 KB Output is correct