oj.uz

Submission #936733

# Submission time Handle Problem Language Result Execution time Memory
936733 2024-03-02T16:05:43 Z velislavgarkov Passport (JOI23_passport) C++14
100 / 100
 786 ms 92776 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define endl '\n'
const int MAXN=2e5+10;
vector <pair <int,int> > v[5*MAXN];
int l[MAXN], r[MAXN], c[MAXN];
int dist[5*MAXN];
priority_queue <pair <int,int> > q;
int n;
void build(int node, int l, int r) {
    if (l==r) {
        v[4*n+l].push_back({node,0});
        return;
    }
    int mid=(l+r)/2;
    v[node*2].push_back({node,0});
    v[node*2+1].push_back({node,0});
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
}
void find_passports(int node, int l, int r, int ql, int qr, int ver) {
    if (ql>r || qr<l) return;
    if (l>=ql && r<=qr) {
        v[node].push_back({ver,1});
        return;
    }
    int mid=(l+r)/2;
    find_passports(node*2,l,mid,ql,qr,ver);
    find_passports(node*2+1,mid+1,r,ql,qr,ver);
}
void dejkstra(int start) {
    memset(dist,-1,sizeof(dist));
    dist[start]=0;
    q.push({0,start});
    while (!q.empty()) {
        int x=q.top().second;
        if (-q.top().first!=dist[x]) {
            q.pop();
            continue;
        }
        q.pop();
        for (auto i:v[x]) {
            if (dist[i.first]==-1 || dist[x]+i.second<dist[i.first]) {
                dist[i.first]=dist[x]+i.second;
                q.push({-dist[i.first],i.first});
            }
        }
    }
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> l[i] >> r[i];
    build(1,1,n);
    for (int i=1;i<=n;i++) {
        c[i]=-1;
        find_passports(1,1,n,l[i],r[i],4*n+i);
    }
    dejkstra(4*n+1);
    dist[4*n+1]=1;
    for (int i=1;i<=n;i++) {
        if (dist[4*n+i]==-1) continue;
        c[i]=dist[4*n+i];
    }
    dejkstra(5*n);
    dist[5*n]=1;
    for (int i=1;i<=n;i++) {
        if (dist[4*n+i]==-1 || c[i]==-1) {
            c[i]=-1;
            continue;
        }
        c[i]+=dist[4*n+i];
    }
    for (int i=1;i<=n;i++) {
        if (c[i]==-1) continue;
        v[5*n+1].push_back({4*n+i,c[i]});
    }
    dejkstra(5*n+1);
    int q, t;
    cin >> q;
    for (int i=0;i<q;i++) {
        cin >> t;
        cout << max(-1,dist[4*n+t]-1) << endl;
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 8 ms 30040 KB Output is correct
3 Correct 9 ms 30044 KB Output is correct
4 Correct 756 ms 83500 KB Output is correct
5 Correct 361 ms 64660 KB Output is correct
6 Correct 217 ms 59244 KB Output is correct
7 Correct 286 ms 56236 KB Output is correct
8 Correct 149 ms 59436 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30040 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 7 ms 30024 KB Output is correct
4 Correct 7 ms 30020 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 8 ms 30044 KB Output is correct
7 Correct 7 ms 30044 KB Output is correct
8 Correct 8 ms 30208 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 8 ms 30044 KB Output is correct
11 Correct 7 ms 30160 KB Output is correct
12 Correct 8 ms 30200 KB Output is correct
13 Correct 8 ms 30044 KB Output is correct
14 Correct 8 ms 30280 KB Output is correct
15 Correct 9 ms 30044 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30040 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 7 ms 30024 KB Output is correct
4 Correct 7 ms 30020 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 8 ms 30044 KB Output is correct
7 Correct 7 ms 30044 KB Output is correct
8 Correct 8 ms 30208 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 8 ms 30044 KB Output is correct
11 Correct 7 ms 30160 KB Output is correct
12 Correct 8 ms 30200 KB Output is correct
13 Correct 8 ms 30044 KB Output is correct
14 Correct 8 ms 30280 KB Output is correct
15 Correct 9 ms 30044 KB Output is correct
16 Correct 13 ms 30556 KB Output is correct
17 Correct 10 ms 30552 KB Output is correct
18 Correct 12 ms 31064 KB Output is correct
19 Correct 11 ms 30812 KB Output is correct
20 Correct 10 ms 30552 KB Output is correct
21 Correct 9 ms 30544 KB Output is correct
22 Correct 9 ms 30556 KB Output is correct
23 Correct 10 ms 30556 KB Output is correct
24 Correct 9 ms 30556 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30040 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 7 ms 30024 KB Output is correct
4 Correct 7 ms 30020 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 8 ms 30044 KB Output is correct
7 Correct 7 ms 30044 KB Output is correct
8 Correct 8 ms 30208 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 8 ms 30044 KB Output is correct
11 Correct 7 ms 30160 KB Output is correct
12 Correct 8 ms 30200 KB Output is correct
13 Correct 8 ms 30044 KB Output is correct
14 Correct 8 ms 30280 KB Output is correct
15 Correct 9 ms 30044 KB Output is correct
16 Correct 13 ms 30556 KB Output is correct
17 Correct 10 ms 30552 KB Output is correct
18 Correct 12 ms 31064 KB Output is correct
19 Correct 11 ms 30812 KB Output is correct
20 Correct 10 ms 30552 KB Output is correct
21 Correct 9 ms 30544 KB Output is correct
22 Correct 9 ms 30556 KB Output is correct
23 Correct 10 ms 30556 KB Output is correct
24 Correct 9 ms 30556 KB Output is correct
25 Correct 7 ms 30044 KB Output is correct
26 Correct 8 ms 30044 KB Output is correct
27 Correct 11 ms 30556 KB Output is correct
28 Correct 13 ms 30556 KB Output is correct
29 Correct 10 ms 30552 KB Output is correct
30 Correct 10 ms 30552 KB Output is correct
31 Correct 11 ms 30544 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30040 KB Output is correct
2 Correct 8 ms 30040 KB Output is correct
3 Correct 9 ms 30044 KB Output is correct
4 Correct 756 ms 83500 KB Output is correct
5 Correct 361 ms 64660 KB Output is correct
6 Correct 217 ms 59244 KB Output is correct
7 Correct 286 ms 56236 KB Output is correct
8 Correct 149 ms 59436 KB Output is correct
9 Correct 7 ms 30040 KB Output is correct
10 Correct 8 ms 30044 KB Output is correct
11 Correct 7 ms 30024 KB Output is correct
12 Correct 7 ms 30020 KB Output is correct
13 Correct 7 ms 30044 KB Output is correct
14 Correct 8 ms 30044 KB Output is correct
15 Correct 7 ms 30044 KB Output is correct
16 Correct 8 ms 30208 KB Output is correct
17 Correct 7 ms 30044 KB Output is correct
18 Correct 8 ms 30044 KB Output is correct
19 Correct 7 ms 30160 KB Output is correct
20 Correct 8 ms 30200 KB Output is correct
21 Correct 8 ms 30044 KB Output is correct
22 Correct 8 ms 30280 KB Output is correct
23 Correct 9 ms 30044 KB Output is correct
24 Correct 13 ms 30556 KB Output is correct
25 Correct 10 ms 30552 KB Output is correct
26 Correct 12 ms 31064 KB Output is correct
27 Correct 11 ms 30812 KB Output is correct
28 Correct 10 ms 30552 KB Output is correct
29 Correct 9 ms 30544 KB Output is correct
30 Correct 9 ms 30556 KB Output is correct
31 Correct 10 ms 30556 KB Output is correct
32 Correct 9 ms 30556 KB Output is correct
33 Correct 7 ms 30044 KB Output is correct
34 Correct 8 ms 30044 KB Output is correct
35 Correct 11 ms 30556 KB Output is correct
36 Correct 13 ms 30556 KB Output is correct
37 Correct 10 ms 30552 KB Output is correct
38 Correct 10 ms 30552 KB Output is correct
39 Correct 11 ms 30544 KB Output is correct
40 Correct 786 ms 87388 KB Output is correct
41 Correct 391 ms 66140 KB Output is correct
42 Correct 461 ms 92776 KB Output is correct
43 Correct 457 ms 92284 KB Output is correct
44 Correct 244 ms 60308 KB Output is correct
45 Correct 256 ms 65904 KB Output is correct
46 Correct 160 ms 42896 KB Output is correct
47 Correct 512 ms 67824 KB Output is correct
48 Correct 323 ms 74268 KB Output is correct