oj.uz

Submission #961898

# Submission time Handle Problem Language Result Execution time Memory
961898 2024-04-12T17:23:57 Z anton Passport (JOI23_passport) C++17
48 / 100
 2000 ms 1048576 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;
    set<int> s;
    for(int i = 0; i<n; i++){
        s.insert(i);
    }
    s.erase(id);
    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(auto it = s.lower_bound(inter[cur].first); it!=s.upper_bound(inter[cur].second);){
            int i = *it;
    
            dist[id][i]  = cur_dist+1;
            q.push({i, cur_dist+1});
            s.erase(it++);
            
        }
    }
}

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:86:13: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
   86 |         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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 2127 ms 1048576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2400 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 8 ms 7004 KB Output is correct
12 Correct 14 ms 6748 KB Output is correct
13 Correct 10 ms 7260 KB Output is correct
14 Correct 9 ms 7216 KB Output is correct
15 Correct 8 ms 6800 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2400 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 8 ms 7004 KB Output is correct
12 Correct 14 ms 6748 KB Output is correct
13 Correct 10 ms 7260 KB Output is correct
14 Correct 9 ms 7216 KB Output is correct
15 Correct 8 ms 6800 KB Output is correct
16 Correct 643 ms 64072 KB Output is correct
17 Correct 793 ms 49496 KB Output is correct
18 Correct 800 ms 81816 KB Output is correct
19 Correct 736 ms 78936 KB Output is correct
20 Correct 722 ms 49584 KB Output is correct
21 Correct 555 ms 54428 KB Output is correct
22 Correct 557 ms 86980 KB Output is correct
23 Correct 747 ms 76344 KB Output is correct
24 Correct 574 ms 77252 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2400 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 8 ms 7004 KB Output is correct
12 Correct 14 ms 6748 KB Output is correct
13 Correct 10 ms 7260 KB Output is correct
14 Correct 9 ms 7216 KB Output is correct
15 Correct 8 ms 6800 KB Output is correct
16 Correct 643 ms 64072 KB Output is correct
17 Correct 793 ms 49496 KB Output is correct
18 Correct 800 ms 81816 KB Output is correct
19 Correct 736 ms 78936 KB Output is correct
20 Correct 722 ms 49584 KB Output is correct
21 Correct 555 ms 54428 KB Output is correct
22 Correct 557 ms 86980 KB Output is correct
23 Correct 747 ms 76344 KB Output is correct
24 Correct 574 ms 77252 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 705 ms 65312 KB Output is correct
28 Correct 812 ms 50000 KB Output is correct
29 Correct 716 ms 49568 KB Output is correct
30 Correct 602 ms 54172 KB Output is correct
31 Correct 666 ms 67784 KB Output is correct

Subtask #5
0 / 46.0

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