oj.uz

Submission #881324

# Submission time Handle Problem Language Result Execution time Memory
881324 2023-12-01T06:46:55 Z ttamx Passport (JOI23_passport) C++14
48 / 100
 336 ms 168716 KB 
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

const int N=2e5+5;
const int M=N+(1<<19);
const int inf=1e9;

int n,q;
vector<p2> adj[M];
int dist[3][M];
bool vis[M];

void link(int u,int v,int w=0){
    adj[v].emplace_back(u,w);
}

void build(int l,int r,int i){
    if(l==r)return void(link(n+i,l));
    int m=(l+r)/2;
    build(l,m,i*2);
    build(m+1,r,i*2+1);
    link(n+i,n+i*2);
    link(n+i,n+i*2+1);
}

void connect(int l,int r,int i,int x,int y,int u){
    if(y<l||r<x)return;
    if(x<=l&&r<=y)return void(link(u,n+i,1));
    int m=(l+r)/2;
    connect(l,m,i*2,x,y,u);
    connect(m+1,r,i*2+1,x,y,u);
}

void dijk(int *dist){
    priority_queue<p2,vector<p2>,greater<p2>> pq;
    for(int i=1;i<=5*n;i++)pq.emplace(dist[i],i),vis[i]=false;
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(auto [v,w]:adj[u])if(d+w<dist[v]){
            pq.emplace(d+w,v);
            dist[v]=d+w;
        }
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    build(1,n,1);
    for(int i=1;i<=n;i++){
        int l,r;
        cin >> l >> r;
        connect(1,n,1,l,r,i);
    }
    for(int i=0;i<3;i++)for(int j=1;j<=5*n;j++)dist[i][j]=inf;
    dist[0][1]=dist[1][n]=0;
    dijk(dist[0]);
    dijk(dist[1]);
    for(int i=1;i<=n;i++)dist[2][i]=min(inf,dist[0][i]+dist[1][i]-(1<i&&i<n));
    dijk(dist[2]);
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << (dist[2][x]<inf?dist[2][x]:-1) << "\n";
    }
}

Compilation message

passport.cpp: In function 'void dijk(int*)':
passport.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [d,u]=pq.top();
      |              ^
passport.cpp:45:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         for(auto [v,w]:adj[u])if(d+w<dist[v]){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24664 KB Output is correct
2 Correct 5 ms 24412 KB Output is correct
3 Correct 5 ms 24260 KB Output is correct
4 Runtime error 336 ms 168716 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24412 KB Output is correct
2 Correct 5 ms 24412 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24244 KB Output is correct
6 Correct 5 ms 24412 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 24436 KB Output is correct
10 Correct 5 ms 24412 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 6 ms 24660 KB Output is correct
13 Correct 6 ms 24412 KB Output is correct
14 Correct 6 ms 24412 KB Output is correct
15 Correct 7 ms 24404 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24412 KB Output is correct
2 Correct 5 ms 24412 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24244 KB Output is correct
6 Correct 5 ms 24412 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 24436 KB Output is correct
10 Correct 5 ms 24412 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 6 ms 24660 KB Output is correct
13 Correct 6 ms 24412 KB Output is correct
14 Correct 6 ms 24412 KB Output is correct
15 Correct 7 ms 24404 KB Output is correct
16 Correct 11 ms 25140 KB Output is correct
17 Correct 13 ms 25040 KB Output is correct
18 Correct 12 ms 25288 KB Output is correct
19 Correct 13 ms 25232 KB Output is correct
20 Correct 11 ms 25012 KB Output is correct
21 Correct 10 ms 24976 KB Output is correct
22 Correct 9 ms 24980 KB Output is correct
23 Correct 11 ms 25064 KB Output is correct
24 Correct 10 ms 25072 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24412 KB Output is correct
2 Correct 5 ms 24412 KB Output is correct
3 Correct 5 ms 24412 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24244 KB Output is correct
6 Correct 5 ms 24412 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 24436 KB Output is correct
10 Correct 5 ms 24412 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 6 ms 24660 KB Output is correct
13 Correct 6 ms 24412 KB Output is correct
14 Correct 6 ms 24412 KB Output is correct
15 Correct 7 ms 24404 KB Output is correct
16 Correct 11 ms 25140 KB Output is correct
17 Correct 13 ms 25040 KB Output is correct
18 Correct 12 ms 25288 KB Output is correct
19 Correct 13 ms 25232 KB Output is correct
20 Correct 11 ms 25012 KB Output is correct
21 Correct 10 ms 24976 KB Output is correct
22 Correct 9 ms 24980 KB Output is correct
23 Correct 11 ms 25064 KB Output is correct
24 Correct 10 ms 25072 KB Output is correct
25 Correct 5 ms 24408 KB Output is correct
26 Correct 5 ms 24412 KB Output is correct
27 Correct 12 ms 25176 KB Output is correct
28 Correct 11 ms 25004 KB Output is correct
29 Correct 12 ms 24980 KB Output is correct
30 Correct 11 ms 25016 KB Output is correct
31 Correct 14 ms 24964 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24664 KB Output is correct
2 Correct 5 ms 24412 KB Output is correct
3 Correct 5 ms 24260 KB Output is correct
4 Runtime error 336 ms 168716 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -