oj.uz

Submission #961889

# Submission time Handle Problem Language Result Execution time Memory
961889 2024-04-12T16:51:46 Z anton Passport (JOI23_passport) C++17
16 / 100
 2000 ms 964312 KB 
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define int long long

const int MAX_N =2501;
const int INF=  1e9;
pii inter[MAX_N];
int dist[MAX_N][MAX_N];
int dp[2][MAX_N];
vector<int> radj[MAX_N];
vector<int> begins[2];
int n;

void BFS(int id){
    queue<pii> q;
    dist[id][id] = 0;
    q.push({id, 0});

    while(q.size()>0){
        int cur= q.front().first;
        int cur_dist = q.front().second;
        //cout<<cur<<" "<<cur_dist<<endl;
        q.pop();
        for(int i = inter[cur].first; i<=inter[cur].second; i++){
            if(dist[id][i] == INF){
                dist[id][i]  = cur_dist+1;
                q.push({i, cur_dist+1});
            }
        }
    }
}

void precalc_dist(){
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++)dist[i][j] = INF;
        BFS(i);
    }
}
signed main(){
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>inter[i].first>>inter[i].second;
        inter[i].first--;
        inter[i].second--;
        for(int j = inter[i].first; j<=inter[i].second; j++){
            radj[j].push_back(i);
        }
        if(inter[i].first==0){
            begins[0].push_back(i);
        }
        if(inter[i].second == n-1){
            begins[1].push_back(i);
        }
    }
    
    
    int q;
    cin>>q;
    precalc_dist();
    for(int c= 0; c<2; c++){
        for(int i = 0; i<n; i++){
            dp[c][i] = INF;
            for(auto e: begins[c]){
                //cout<<c<<" "<<i<<" "<<e<<" "<<dist[i][e]+1<<endl;
                dp[c][i] = min(dp[c][i], dist[i][e]+1);
            }
        }
    }

    for(int i = 0; i<q; i++){
        int v;
        cin>>v;
        v--;
        int res= INF;
        int mid= v;
        for(int j = 0; j<n; j++){
            //cout<<dist[v][j]<<end
            if(dp[0][j]-1 + dp[1][j] + dist[v][j]<res){
                //cout<<v<<" "<<j<<endl;
                //cout<<dpr.tr[j+dpr.sz]<<" "<<dpl.tr[j+dpl.sz]<<" "<<dist[v][j]<<endl;
                mid= j;
            }
            res= min(res, dp[0][j]-1 + dp[1][j] + dist[v][j]);
            
        }
        if(res>=INF){
            cout<<-1<<endl;
        }
        else{
            cout<<res<<" "<<endl;
        }
    }
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:78:13: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
   78 |         int mid= v;
      |             ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2138 ms 964312 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 2 ms 2556 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 5 ms 7000 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct
13 Correct 10 ms 7272 KB Output is correct
14 Correct 12 ms 7004 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 2 ms 2556 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 5 ms 7000 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct
13 Correct 10 ms 7272 KB Output is correct
14 Correct 12 ms 7004 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 1655 ms 64148 KB Output is correct
17 Correct 147 ms 49428 KB Output is correct
18 Execution timed out 2061 ms 57964 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 2 ms 2556 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 5 ms 7000 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct
13 Correct 10 ms 7272 KB Output is correct
14 Correct 12 ms 7004 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 1655 ms 64148 KB Output is correct
17 Correct 147 ms 49428 KB Output is correct
18 Execution timed out 2061 ms 57964 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2138 ms 964312 KB Time limit exceeded
5 Halted 0 ms 0 KB -