oj.uz

Submission #1084375

# Submission time Handle Problem Language Result Execution time Memory
1084375 2024-09-06T06:50:15 Z Bananabread Passport (JOI23_passport) C++17
0 / 100
 2000 ms 108956 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<pair<ll,ll>> adj[800001];
ll id[200001];
void build(ll pos,ll l,ll r){
    if(l==r){
        id[l]=pos;
    }
    else{
        ll mid=(l+r)/2;
        build(2*pos,l,mid);
        build(2*pos+1,mid+1,r);
        adj[pos].push_back({2*pos,0});
        adj[pos].push_back({2*pos+1,0});
    }
}
void add(ll pos,ll l,ll r,ll u,ll v,ll x){
    if(v<l||u>r) return ;
    else if(u<=l&&r<=v){
        adj[id[x]].push_back({pos,1});
    }
    else{
        ll mid=(l+r)/2;
        add(2*pos,l,mid,u,v,x);
        add(2*pos+1,mid+1,r,u,v,x);
    }
}
ll n,q;
ll ans[800001];
ll dist[800001];
ll vis[800001];
void proc(ll st){
    fill(dist+1,dist+4*n+1,1e18);
    fill(vis+1,vis+4*n+1,0);
    deque<ll> dq;
    dq.push_front(id[st]);
    dist[id[st]]=0;
    while(!dq.empty()){
        ll u=dq.front();
        dq.pop_front();
        if(vis[u]) continue;
      	vis[u]=1;
        for(auto [v,w]:adj[u]){
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(w==0){
                    dq.push_front(v);
                }
                else{
                    dq.push_back(v);
                }
            }
        }
    }
    ll mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,dist[id[i]]);
    }
    if(mx==1e18) ans[st]=-1;
    else ans[st]=mx;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        ll l,r;
        cin>>l>>r;
        add(1,1,n,l,r,i);
    }
    for(int i=1;i<=n;i++){
        proc(i);
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        cout<<ans[x]<<ntr;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 9 ms 19024 KB Output is correct
4 Execution timed out 2048 ms 108956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 9 ms 19036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 9 ms 19024 KB Output is correct
4 Execution timed out 2048 ms 108956 KB Time limit exceeded
5 Halted 0 ms 0 KB -