oj.uz

Submission #1085897

# Submission time Handle Problem Language Result Execution time Memory
1085897 2024-09-09T02:46:15 Z Bananabread Passport (JOI23_passport) C++17
48 / 100
 1008 ms 904088 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<array<int,3>> adj[2501][2501];
ll dist[2501][2501];
ll vis[2501][2501];
ll n,q;
ll l[2501];
ll r[2501];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n;i++){
        ll mx=0,mn=1e18;
        adj[l[i]][r[i]].push_back({i,i,1});
        for(int j=i;j<=n;j++){
            mx=max(mx,r[j]);
            mn=min(mn,l[j]);
            if(i!=j){
                //cout<<i<<' '<<j<<' '<<mn<<' '<<mx<<ntr;
                adj[i][mx].push_back({i,j,1});
                adj[mn][j].push_back({i,j,1});
                adj[i+1][j].push_back({i,j,0});
                adj[i][j-1].push_back({i,j,0});
            }
        }
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1][n]=0;
    deque<array<ll,2>> dq;
    dq.push_front({1,n});
    while(!dq.empty()){
        ll u=dq.front()[0],v=dq.front()[1];
        dq.pop_front();
        if(vis[u][v]) continue;
        vis[u][v]=1;
        for(auto i:adj[u][v]){
            ll x=i[0],y=i[1],w=i[2];
            if(dist[x][y]>dist[u][v]+w){
                dist[x][y]=dist[u][v]+w;
                if(w==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            cout<<dist[i][j]<<' ';
//        }
//        cout<<ntr;
//    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        cout<<(dist[x][x] >= 1e18 ? -1 : dist[x][x])<<ntr;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196172 KB Output is correct
2 Correct 80 ms 196176 KB Output is correct
3 Correct 84 ms 196176 KB Output is correct
4 Runtime error 1008 ms 904088 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 84 ms 196208 KB Output is correct
2 Correct 84 ms 196192 KB Output is correct
3 Correct 86 ms 196192 KB Output is correct
4 Correct 83 ms 196288 KB Output is correct
5 Correct 82 ms 196304 KB Output is correct
6 Correct 82 ms 196192 KB Output is correct
7 Correct 83 ms 196104 KB Output is correct
8 Correct 84 ms 196200 KB Output is correct
9 Correct 84 ms 196236 KB Output is correct
10 Correct 78 ms 196116 KB Output is correct
11 Correct 88 ms 200800 KB Output is correct
12 Correct 94 ms 200804 KB Output is correct
13 Correct 90 ms 201056 KB Output is correct
14 Correct 95 ms 201060 KB Output is correct
15 Correct 90 ms 200800 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196208 KB Output is correct
2 Correct 84 ms 196192 KB Output is correct
3 Correct 86 ms 196192 KB Output is correct
4 Correct 83 ms 196288 KB Output is correct
5 Correct 82 ms 196304 KB Output is correct
6 Correct 82 ms 196192 KB Output is correct
7 Correct 83 ms 196104 KB Output is correct
8 Correct 84 ms 196200 KB Output is correct
9 Correct 84 ms 196236 KB Output is correct
10 Correct 78 ms 196116 KB Output is correct
11 Correct 88 ms 200800 KB Output is correct
12 Correct 94 ms 200804 KB Output is correct
13 Correct 90 ms 201056 KB Output is correct
14 Correct 95 ms 201060 KB Output is correct
15 Correct 90 ms 200800 KB Output is correct
16 Correct 579 ms 427148 KB Output is correct
17 Correct 776 ms 448608 KB Output is correct
18 Correct 613 ms 438644 KB Output is correct
19 Correct 560 ms 433400 KB Output is correct
20 Correct 618 ms 425464 KB Output is correct
21 Correct 721 ms 451304 KB Output is correct
22 Correct 487 ms 436232 KB Output is correct
23 Correct 650 ms 455684 KB Output is correct
24 Correct 552 ms 449796 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196208 KB Output is correct
2 Correct 84 ms 196192 KB Output is correct
3 Correct 86 ms 196192 KB Output is correct
4 Correct 83 ms 196288 KB Output is correct
5 Correct 82 ms 196304 KB Output is correct
6 Correct 82 ms 196192 KB Output is correct
7 Correct 83 ms 196104 KB Output is correct
8 Correct 84 ms 196200 KB Output is correct
9 Correct 84 ms 196236 KB Output is correct
10 Correct 78 ms 196116 KB Output is correct
11 Correct 88 ms 200800 KB Output is correct
12 Correct 94 ms 200804 KB Output is correct
13 Correct 90 ms 201056 KB Output is correct
14 Correct 95 ms 201060 KB Output is correct
15 Correct 90 ms 200800 KB Output is correct
16 Correct 579 ms 427148 KB Output is correct
17 Correct 776 ms 448608 KB Output is correct
18 Correct 613 ms 438644 KB Output is correct
19 Correct 560 ms 433400 KB Output is correct
20 Correct 618 ms 425464 KB Output is correct
21 Correct 721 ms 451304 KB Output is correct
22 Correct 487 ms 436232 KB Output is correct
23 Correct 650 ms 455684 KB Output is correct
24 Correct 552 ms 449796 KB Output is correct
25 Correct 86 ms 196180 KB Output is correct
26 Correct 92 ms 196176 KB Output is correct
27 Correct 573 ms 447824 KB Output is correct
28 Correct 819 ms 452176 KB Output is correct
29 Correct 605 ms 425556 KB Output is correct
30 Correct 564 ms 451412 KB Output is correct
31 Correct 548 ms 454864 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 196172 KB Output is correct
2 Correct 80 ms 196176 KB Output is correct
3 Correct 84 ms 196176 KB Output is correct
4 Runtime error 1008 ms 904088 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -