답안 #928721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928721	2024-02-17T02:37:13 Z	Darren0724	Passport (JOI23_passport)	C++17	100 / 100	874 ms	124152 KB

passport

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int M=N*5;
const int INF=1e8;
int n;
vector dis(3,vector(M,INF));
vector<pair<int,int>> adj[M],adj1[M];
vector<int> rec(N);
void link(int a,int b,int c){
    adj[b].push_back({a,c});
}
void build(int id=1,int l=1,int r=n+1){
    if(r-l==1)return link(n+id,l,1);
    int m=(l+r)>>1;
    link(n+id,n+id*2,0);
    link(n+id,n+id*2+1,0);
    build(id<<1,l,m);
    build(id<<1|1,m,r);
}
void connect(int id,int l,int r,int a,int b,int x){
    if(a<=l&&b>=r)return link(x,n+id,0);
    if(r-l==1)return;
    int m=(l+r)>>1;
    if(a<m)connect(id<<1,l,m,a,b,x);
    if(b>m)connect(id<<1|1,m,r,a,b,x);
}
void dijk(vector<int> &dis){
    priority_queue<pair<int,int>> pq;
    for(int i=1;i<=n;i++){
        pq.push({-dis[i],i});
    }
    while(pq.size()){
        auto [a,b]=pq.top();
        pq.pop();
        a=-a;
        if(dis[b]!=a)continue;
        for(auto [c,d]:adj[b]){
            int cost=dis[b]+d;
            if(cost<dis[c]){
                dis[c]=cost;
                pq.push({-cost,c});
            }
        }
    }
}
int32_t main() {
    LCBorz;
    cin>>n;
    build();
    vector<int> b(N),c(N);
    for(int i=1;i<=n;i++){
        cin>>b[i]>>c[i];
        connect(1,1,n+1,b[i],c[i]+1,i);
    }
    dis[0][1]=dis[1][n]=0;
    dijk(dis[0]);
    dijk(dis[1]);
    for(int i=1;i<=n;i++){
        dis[2][i]=dis[0][i]+dis[1][i]-(1<i&&i<n);
    }
    dijk(dis[2]);
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int p;cin>>p;
        cout<<(dis[2][p]>=INF?-1:dis[2][p])<<endl;
    }

    return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	61464 KB	Output is correct
2	Correct	16 ms	61540 KB	Output is correct
3	Correct	17 ms	61356 KB	Output is correct
4	Correct	838 ms	117072 KB	Output is correct
5	Correct	432 ms	92912 KB	Output is correct
6	Correct	340 ms	87164 KB	Output is correct
7	Correct	364 ms	88352 KB	Output is correct
8	Correct	187 ms	81372 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	61464 KB	Output is correct
2	Correct	17 ms	61500 KB	Output is correct
3	Correct	18 ms	61420 KB	Output is correct
4	Correct	21 ms	61528 KB	Output is correct
5	Correct	18 ms	61448 KB	Output is correct
6	Correct	18 ms	61464 KB	Output is correct
7	Correct	19 ms	61464 KB	Output is correct
8	Correct	17 ms	61464 KB	Output is correct
9	Correct	17 ms	61464 KB	Output is correct
10	Correct	17 ms	61392 KB	Output is correct
11	Correct	17 ms	61464 KB	Output is correct
12	Correct	20 ms	61464 KB	Output is correct
13	Correct	22 ms	61464 KB	Output is correct
14	Correct	23 ms	61464 KB	Output is correct
15	Correct	19 ms	61416 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	61464 KB	Output is correct
2	Correct	17 ms	61500 KB	Output is correct
3	Correct	18 ms	61420 KB	Output is correct
4	Correct	21 ms	61528 KB	Output is correct
5	Correct	18 ms	61448 KB	Output is correct
6	Correct	18 ms	61464 KB	Output is correct
7	Correct	19 ms	61464 KB	Output is correct
8	Correct	17 ms	61464 KB	Output is correct
9	Correct	17 ms	61464 KB	Output is correct
10	Correct	17 ms	61392 KB	Output is correct
11	Correct	17 ms	61464 KB	Output is correct
12	Correct	20 ms	61464 KB	Output is correct
13	Correct	22 ms	61464 KB	Output is correct
14	Correct	23 ms	61464 KB	Output is correct
15	Correct	19 ms	61416 KB	Output is correct
16	Correct	22 ms	61988 KB	Output is correct
17	Correct	22 ms	61940 KB	Output is correct
18	Correct	23 ms	61920 KB	Output is correct
19	Correct	24 ms	62116 KB	Output is correct
20	Correct	21 ms	61696 KB	Output is correct
21	Correct	22 ms	61876 KB	Output is correct
22	Correct	20 ms	61716 KB	Output is correct
23	Correct	23 ms	61968 KB	Output is correct
24	Correct	23 ms	62000 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	61464 KB	Output is correct
2	Correct	17 ms	61500 KB	Output is correct
3	Correct	18 ms	61420 KB	Output is correct
4	Correct	21 ms	61528 KB	Output is correct
5	Correct	18 ms	61448 KB	Output is correct
6	Correct	18 ms	61464 KB	Output is correct
7	Correct	19 ms	61464 KB	Output is correct
8	Correct	17 ms	61464 KB	Output is correct
9	Correct	17 ms	61464 KB	Output is correct
10	Correct	17 ms	61392 KB	Output is correct
11	Correct	17 ms	61464 KB	Output is correct
12	Correct	20 ms	61464 KB	Output is correct
13	Correct	22 ms	61464 KB	Output is correct
14	Correct	23 ms	61464 KB	Output is correct
15	Correct	19 ms	61416 KB	Output is correct
16	Correct	22 ms	61988 KB	Output is correct
17	Correct	22 ms	61940 KB	Output is correct
18	Correct	23 ms	61920 KB	Output is correct
19	Correct	24 ms	62116 KB	Output is correct
20	Correct	21 ms	61696 KB	Output is correct
21	Correct	22 ms	61876 KB	Output is correct
22	Correct	20 ms	61716 KB	Output is correct
23	Correct	23 ms	61968 KB	Output is correct
24	Correct	23 ms	62000 KB	Output is correct
25	Correct	19 ms	61460 KB	Output is correct
26	Correct	21 ms	61416 KB	Output is correct
27	Correct	24 ms	62052 KB	Output is correct
28	Correct	23 ms	61968 KB	Output is correct
29	Correct	22 ms	61896 KB	Output is correct
30	Correct	20 ms	61788 KB	Output is correct
31	Correct	23 ms	61900 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	61464 KB	Output is correct
2	Correct	16 ms	61540 KB	Output is correct
3	Correct	17 ms	61356 KB	Output is correct
4	Correct	838 ms	117072 KB	Output is correct
5	Correct	432 ms	92912 KB	Output is correct
6	Correct	340 ms	87164 KB	Output is correct
7	Correct	364 ms	88352 KB	Output is correct
8	Correct	187 ms	81372 KB	Output is correct
9	Correct	21 ms	61464 KB	Output is correct
10	Correct	17 ms	61500 KB	Output is correct
11	Correct	18 ms	61420 KB	Output is correct
12	Correct	21 ms	61528 KB	Output is correct
13	Correct	18 ms	61448 KB	Output is correct
14	Correct	18 ms	61464 KB	Output is correct
15	Correct	19 ms	61464 KB	Output is correct
16	Correct	17 ms	61464 KB	Output is correct
17	Correct	17 ms	61464 KB	Output is correct
18	Correct	17 ms	61392 KB	Output is correct
19	Correct	17 ms	61464 KB	Output is correct
20	Correct	20 ms	61464 KB	Output is correct
21	Correct	22 ms	61464 KB	Output is correct
22	Correct	23 ms	61464 KB	Output is correct
23	Correct	19 ms	61416 KB	Output is correct
24	Correct	22 ms	61988 KB	Output is correct
25	Correct	22 ms	61940 KB	Output is correct
26	Correct	23 ms	61920 KB	Output is correct
27	Correct	24 ms	62116 KB	Output is correct
28	Correct	21 ms	61696 KB	Output is correct
29	Correct	22 ms	61876 KB	Output is correct
30	Correct	20 ms	61716 KB	Output is correct
31	Correct	23 ms	61968 KB	Output is correct
32	Correct	23 ms	62000 KB	Output is correct
33	Correct	19 ms	61460 KB	Output is correct
34	Correct	21 ms	61416 KB	Output is correct
35	Correct	24 ms	62052 KB	Output is correct
36	Correct	23 ms	61968 KB	Output is correct
37	Correct	22 ms	61896 KB	Output is correct
38	Correct	20 ms	61788 KB	Output is correct
39	Correct	23 ms	61900 KB	Output is correct
40	Correct	874 ms	116380 KB	Output is correct
41	Correct	472 ms	94128 KB	Output is correct
42	Correct	544 ms	120736 KB	Output is correct
43	Correct	509 ms	124152 KB	Output is correct
44	Correct	354 ms	88436 KB	Output is correct
45	Correct	383 ms	95620 KB	Output is correct
46	Correct	217 ms	73688 KB	Output is correct
47	Correct	685 ms	101240 KB	Output is correct
48	Correct	439 ms	107816 KB	Output is correct

답안 #928721

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 8.0 / 8.0

Subtask #5 46.0 / 46.0

Subtask #1
6.0 / 6.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
8.0 / 8.0

Subtask #5
46.0 / 46.0