oj.uz

Submission #793670

# Submission time Handle Problem Language Result Execution time Memory
793670 2023-07-26T05:26:33 Z vjudge1 Passport (JOI23_passport) C++17
6 / 100
 1056 ms 98264 KB 
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;
const int mod = 1e9 + 7;

using namespace std;

int n;
int S;
int a[N], b[N];
vector<pair<int, int>> v[4 * N];

void upd(int x, int l, int r, int tl, int tr, int g)
{
    if (tl > tr) {
        return;
    } else if (l == tl && r == tr) {
        v[x].push_back({g, 1});
        return;
    }
    int m = (l + r) / 2;
    upd(x * 2, l, m, tl, min(m, tr), g);
    upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, g);
}

void solve(vector<int> &d)
{
    set<pair<int, int>> s;
    for (int i = 0; i < d.size(); i++) {
        s.insert({d[i], i});
    }
    while (!s.empty()) {
        int x = s.begin()->se;
        s.erase(s.begin());
        for (auto y: v[x]) {
            if (d[x] + y.se < d[y.fi]) {
                s.erase({d[y.fi], y.fi});
                d[y.fi] = d[x] + y.se;
                s.insert({d[y.fi], y.fi});
            }
        }
    }
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n;

    S = 2;
    while (S < n) {
        S *= 2;
    }

    for (int i = 1; i < S; i++) {
        v[i * 2].push_back({i, 0});
        v[i * 2 + 1].push_back({i, 0});
    }

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];

        a[i]--;
        b[i]--;

        upd(1, 0, S - 1, a[i], b[i], S + i);
    }

    int inf = 1e9;
    vector<int> A(2 * S, inf), B(2 * S, inf), C(2 * S, inf);
    A[S] = 0;
    B[S + n - 1] = 0;

    solve(A);
    solve(B);

    for (int i = 0; i < 2 * S; i++) {
        C[i] = A[i] + B[i];
        C[i] = min(C[i], inf);
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == 0 && b[i] == n - 1) {
            C[S + i] = 1;
        }
    }

    solve(C);

    for (int i = 0; i < 2* S; i++) {
        if (C[i] >= inf) {
            C[i] = -1;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << C[S + x - 1] << "\n";
    }
}

Compilation message

passport.cpp: In function 'void solve(std::vector<int>&)':
passport.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < d.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19072 KB Output is correct
3 Correct 10 ms 19088 KB Output is correct
4 Correct 1056 ms 98264 KB Output is correct
5 Correct 613 ms 78500 KB Output is correct
6 Correct 472 ms 75164 KB Output is correct
7 Correct 549 ms 86412 KB Output is correct
8 Correct 411 ms 87904 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 10 ms 19032 KB Output is correct
4 Correct 10 ms 19028 KB Output is correct
5 Correct 13 ms 19132 KB Output is correct
6 Correct 12 ms 19104 KB Output is correct
7 Correct 12 ms 19040 KB Output is correct
8 Incorrect 10 ms 19084 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 10 ms 19032 KB Output is correct
4 Correct 10 ms 19028 KB Output is correct
5 Correct 13 ms 19132 KB Output is correct
6 Correct 12 ms 19104 KB Output is correct
7 Correct 12 ms 19040 KB Output is correct
8 Incorrect 10 ms 19084 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Correct 10 ms 19032 KB Output is correct
4 Correct 10 ms 19028 KB Output is correct
5 Correct 13 ms 19132 KB Output is correct
6 Correct 12 ms 19104 KB Output is correct
7 Correct 12 ms 19040 KB Output is correct
8 Incorrect 10 ms 19084 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19072 KB Output is correct
3 Correct 10 ms 19088 KB Output is correct
4 Correct 1056 ms 98264 KB Output is correct
5 Correct 613 ms 78500 KB Output is correct
6 Correct 472 ms 75164 KB Output is correct
7 Correct 549 ms 86412 KB Output is correct
8 Correct 411 ms 87904 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 11 ms 19028 KB Output is correct
11 Correct 10 ms 19032 KB Output is correct
12 Correct 10 ms 19028 KB Output is correct
13 Correct 13 ms 19132 KB Output is correct
14 Correct 12 ms 19104 KB Output is correct
15 Correct 12 ms 19040 KB Output is correct
16 Incorrect 10 ms 19084 KB Output isn't correct
17 Halted 0 ms 0 KB -