oj.uz

Submission #737633

# Submission time Handle Problem Language Result Execution time Memory
737633 2023-05-07T12:51:12 Z He_Huanglu Passport (JOI23_passport) C++17
100 / 100
 925 ms 98152 KB 
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 3e5 + 5;
int n, nq, d[4 * N][2], f[4 * N], id[N];
bool ok[4 * N];
vector <ii> ke[4 * N];

void build(int i, int l, int r) {
    if(l == r) {
        id[l] = i;
        ok[i] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    ke[i << 1].push_back({i, 0});
    ke[i << 1 | 1].push_back({i, 0});
}

void join(int x, int i, int l, int r, int u, int v) {
    if(l > v || u > r) return ;
    if(u <= l && r <= v) {
        if(id[x] != i) ke[i].push_back({id[x], 1});
        return ;
    }
    int mid = l + r >> 1;
    join(x, i << 1, l, mid, u, v);
    join(x, i << 1 | 1, mid + 1, r, u, v);
}

void dij(int x, int j) {
    priority_queue <ii, vector <ii>, greater <ii> > pq;
    d[x][j] = 0;
    pq.push({d[x][j], x});
    while (!pq.empty()) {
        ii e = pq.top();
        pq.pop();
        if(e.fi != d[e.se][j]) continue;
        for(auto [v, w] : ke[e.se]) if(d[v][j] > e.fi + w) {
            d[v][j] = e.fi + w;
            pq.push({d[v][j], v});
        }
    }
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        join(i, 1, 1, n, l, r);
    }
    memset(d, 60, sizeof d);
    dij(id[1], 0);
    dij(id[n], 1);
    priority_queue <ii, vector <ii>, greater <ii> > pq;
    for(int i = 1; i <= 4 * n; i++) {
        f[i] = d[i][0] + d[i][1] - ((i == id[1] || i == id[n]) ? 0 : ok[i]);
        pq.push({f[i], i});
    }
    while (!pq.empty()) {
        ii e = pq.top();
        pq.pop();
        if(e.fi != f[e.se]) continue;
        for(auto [v, w] : ke[e.se]) if(f[v] > e.fi + w) {
            f[v] = e.fi + w;
            pq.push({f[v], v});
        }
    }
    cin >> nq;
    for(int i = 1; i <= nq; i++) {
        int x; cin >> x;
        x = id[x];
        cout << (f[x] > n ? -1 : f[x]) << "\n";
    }
    return 0;
}

Compilation message

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void join(int, int, int, int, int, int)':
passport.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: At global scope:
passport.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main () {
      | ^~~~
passport.cpp: In function 'int main()':
passport.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37836 KB Output is correct
2 Correct 22 ms 37848 KB Output is correct
3 Correct 20 ms 37844 KB Output is correct
4 Correct 820 ms 90536 KB Output is correct
5 Correct 397 ms 70416 KB Output is correct
6 Correct 236 ms 62496 KB Output is correct
7 Correct 289 ms 63392 KB Output is correct
8 Correct 247 ms 70808 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37908 KB Output is correct
2 Correct 18 ms 37900 KB Output is correct
3 Correct 20 ms 37840 KB Output is correct
4 Correct 20 ms 37804 KB Output is correct
5 Correct 19 ms 37784 KB Output is correct
6 Correct 19 ms 37784 KB Output is correct
7 Correct 20 ms 37912 KB Output is correct
8 Correct 19 ms 37844 KB Output is correct
9 Correct 21 ms 37940 KB Output is correct
10 Correct 19 ms 37844 KB Output is correct
11 Correct 20 ms 37956 KB Output is correct
12 Correct 19 ms 37972 KB Output is correct
13 Correct 22 ms 37876 KB Output is correct
14 Correct 23 ms 37972 KB Output is correct
15 Correct 21 ms 37972 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37908 KB Output is correct
2 Correct 18 ms 37900 KB Output is correct
3 Correct 20 ms 37840 KB Output is correct
4 Correct 20 ms 37804 KB Output is correct
5 Correct 19 ms 37784 KB Output is correct
6 Correct 19 ms 37784 KB Output is correct
7 Correct 20 ms 37912 KB Output is correct
8 Correct 19 ms 37844 KB Output is correct
9 Correct 21 ms 37940 KB Output is correct
10 Correct 19 ms 37844 KB Output is correct
11 Correct 20 ms 37956 KB Output is correct
12 Correct 19 ms 37972 KB Output is correct
13 Correct 22 ms 37876 KB Output is correct
14 Correct 23 ms 37972 KB Output is correct
15 Correct 21 ms 37972 KB Output is correct
16 Correct 25 ms 38484 KB Output is correct
17 Correct 26 ms 38336 KB Output is correct
18 Correct 23 ms 38576 KB Output is correct
19 Correct 25 ms 38612 KB Output is correct
20 Correct 22 ms 38356 KB Output is correct
21 Correct 23 ms 38356 KB Output is correct
22 Correct 22 ms 38356 KB Output is correct
23 Correct 24 ms 38416 KB Output is correct
24 Correct 24 ms 38484 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37908 KB Output is correct
2 Correct 18 ms 37900 KB Output is correct
3 Correct 20 ms 37840 KB Output is correct
4 Correct 20 ms 37804 KB Output is correct
5 Correct 19 ms 37784 KB Output is correct
6 Correct 19 ms 37784 KB Output is correct
7 Correct 20 ms 37912 KB Output is correct
8 Correct 19 ms 37844 KB Output is correct
9 Correct 21 ms 37940 KB Output is correct
10 Correct 19 ms 37844 KB Output is correct
11 Correct 20 ms 37956 KB Output is correct
12 Correct 19 ms 37972 KB Output is correct
13 Correct 22 ms 37876 KB Output is correct
14 Correct 23 ms 37972 KB Output is correct
15 Correct 21 ms 37972 KB Output is correct
16 Correct 25 ms 38484 KB Output is correct
17 Correct 26 ms 38336 KB Output is correct
18 Correct 23 ms 38576 KB Output is correct
19 Correct 25 ms 38612 KB Output is correct
20 Correct 22 ms 38356 KB Output is correct
21 Correct 23 ms 38356 KB Output is correct
22 Correct 22 ms 38356 KB Output is correct
23 Correct 24 ms 38416 KB Output is correct
24 Correct 24 ms 38484 KB Output is correct
25 Correct 21 ms 37824 KB Output is correct
26 Correct 20 ms 37836 KB Output is correct
27 Correct 24 ms 38484 KB Output is correct
28 Correct 24 ms 38356 KB Output is correct
29 Correct 22 ms 38320 KB Output is correct
30 Correct 22 ms 38424 KB Output is correct
31 Correct 24 ms 38412 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37836 KB Output is correct
2 Correct 22 ms 37848 KB Output is correct
3 Correct 20 ms 37844 KB Output is correct
4 Correct 820 ms 90536 KB Output is correct
5 Correct 397 ms 70416 KB Output is correct
6 Correct 236 ms 62496 KB Output is correct
7 Correct 289 ms 63392 KB Output is correct
8 Correct 247 ms 70808 KB Output is correct
9 Correct 19 ms 37908 KB Output is correct
10 Correct 18 ms 37900 KB Output is correct
11 Correct 20 ms 37840 KB Output is correct
12 Correct 20 ms 37804 KB Output is correct
13 Correct 19 ms 37784 KB Output is correct
14 Correct 19 ms 37784 KB Output is correct
15 Correct 20 ms 37912 KB Output is correct
16 Correct 19 ms 37844 KB Output is correct
17 Correct 21 ms 37940 KB Output is correct
18 Correct 19 ms 37844 KB Output is correct
19 Correct 20 ms 37956 KB Output is correct
20 Correct 19 ms 37972 KB Output is correct
21 Correct 22 ms 37876 KB Output is correct
22 Correct 23 ms 37972 KB Output is correct
23 Correct 21 ms 37972 KB Output is correct
24 Correct 25 ms 38484 KB Output is correct
25 Correct 26 ms 38336 KB Output is correct
26 Correct 23 ms 38576 KB Output is correct
27 Correct 25 ms 38612 KB Output is correct
28 Correct 22 ms 38356 KB Output is correct
29 Correct 23 ms 38356 KB Output is correct
30 Correct 22 ms 38356 KB Output is correct
31 Correct 24 ms 38416 KB Output is correct
32 Correct 24 ms 38484 KB Output is correct
33 Correct 21 ms 37824 KB Output is correct
34 Correct 20 ms 37836 KB Output is correct
35 Correct 24 ms 38484 KB Output is correct
36 Correct 24 ms 38356 KB Output is correct
37 Correct 22 ms 38320 KB Output is correct
38 Correct 22 ms 38424 KB Output is correct
39 Correct 24 ms 38412 KB Output is correct
40 Correct 925 ms 91144 KB Output is correct
41 Correct 443 ms 71084 KB Output is correct
42 Correct 527 ms 98152 KB Output is correct
43 Correct 544 ms 97336 KB Output is correct
44 Correct 263 ms 63264 KB Output is correct
45 Correct 337 ms 71076 KB Output is correct
46 Correct 184 ms 51192 KB Output is correct
47 Correct 530 ms 73572 KB Output is correct
48 Correct 449 ms 81304 KB Output is correct