oj.uz

Submission #849993

# Submission time Handle Problem Language Result Execution time Memory
849993 2023-09-15T15:23:59 Z Ahmed57 Event Hopping (BOI22_events) C++17
30 / 100
 707 ms 33796 KB 
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.first.second<b.first.second;
}
int P[100001][17],ind[100001];
vector<int> adj[100001];
signed main(){
    int n,q;cin>>n>>q;
    if(n<=1000){
        vector<pair<int,int>> v;
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        v.push_back({a,b});
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(i!=j){
                if(v[j].first<=v[i].second&&v[i].second<=v[j].second){
                    adj[i].push_back(j);
                }
            }
        }
    }
    vector<pair<int,int>> qu[n];
    for(int i = 0;i<q;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        qu[a].push_back({b,i});
    }
    int ans[q] = {0};
    int cost[n] = {0};
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cost[j] = 1e9;;
        }
        queue<int> q;q.push(i);
        cost[i] = 0;
        while(!q.empty()){
            int x = q.front();q.pop();
            for(auto j:adj[x]){
                if(cost[j]==1e9){
                    cost[j] = cost[x]+1;
                    q.push(j);
                }
            }
        }
        for(auto j:qu[i]){
            ans[j.second] = cost[j.first];
        }
    }
    for(int i = 0;i<q;i++){
        if(ans[i]==1e9)cout<<"impossible\n";
        else cout<<ans[i]<<"\n";
    }
    return 0;
    }
    vector<pair<pair<int,int>,int>> v;
    map<int,int> comp,sav;
    for(int i = 0;i<n;i++){
        int a,b;
        cin>>a>>b;
        comp[a]++;comp[b]++;
        v.push_back({{a,b},i});
    }
    long long z = 0;
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    for(int i = 0;i<n;i++){
        v[i].first.first = sav[v[i].first.first];
        v[i].first.second = sav[v[i].first.second];
    }
    sort(v.begin(),v.end(),cmp);
    int in = 0;
    for(int i = 0;i<v.size();i++){
        ind[v[i].second] = i;
        while(in<n&&v[in].first.first<=v[i].first.second){
            in++;
        }
        P[i][0] = in-1;
    }
    for(int i = n-1;i>=0;i--){
        for(int j = 1;j<17;j++){
            P[i][j] = P[P[i][j-1]][j-1];
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        a--;b--;
        if(ind[a]>ind[b]){
        cout<<"impossible\n";
        continue;
        }else if(ind[a]==ind[b]){
        cout<<0<<endl;
        continue;
        }
        int sum = 0 , cur = ind[a];
        for(int i = 16;i>=0;i--){
            if(v[P[cur][i]].first.second<v[ind[b]].first.second){
                sum+=(1<<i);
                cur = P[cur][i];
            }
        }
        if(v[P[cur][0]].first.second>=v[ind[b]].first.second){
            cout<<sum+1<<endl;
        }else cout<<"impossible\n";
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 326 ms 20900 KB Output is correct
3 Correct 334 ms 23904 KB Output is correct
4 Correct 330 ms 23892 KB Output is correct
5 Incorrect 326 ms 25348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 10 ms 4700 KB Output is correct
4 Correct 8 ms 4728 KB Output is correct
5 Correct 10 ms 4700 KB Output is correct
6 Correct 38 ms 5544 KB Output is correct
7 Correct 105 ms 6340 KB Output is correct
8 Correct 125 ms 7396 KB Output is correct
9 Correct 707 ms 8744 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 10 ms 4700 KB Output is correct
4 Correct 8 ms 4728 KB Output is correct
5 Correct 10 ms 4700 KB Output is correct
6 Correct 38 ms 5544 KB Output is correct
7 Correct 105 ms 6340 KB Output is correct
8 Correct 125 ms 7396 KB Output is correct
9 Correct 707 ms 8744 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 10 ms 4700 KB Output is correct
13 Correct 7 ms 4780 KB Output is correct
14 Correct 10 ms 4700 KB Output is correct
15 Correct 41 ms 5468 KB Output is correct
16 Correct 109 ms 6348 KB Output is correct
17 Correct 132 ms 7396 KB Output is correct
18 Correct 668 ms 8744 KB Output is correct
19 Correct 167 ms 5716 KB Output is correct
20 Correct 171 ms 6636 KB Output is correct
21 Incorrect 168 ms 6952 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 10 ms 4700 KB Output is correct
4 Correct 8 ms 4728 KB Output is correct
5 Correct 10 ms 4700 KB Output is correct
6 Correct 38 ms 5544 KB Output is correct
7 Correct 105 ms 6340 KB Output is correct
8 Correct 125 ms 7396 KB Output is correct
9 Correct 707 ms 8744 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 10 ms 4748 KB Output is correct
13 Correct 7 ms 4700 KB Output is correct
14 Correct 10 ms 4700 KB Output is correct
15 Correct 38 ms 5468 KB Output is correct
16 Correct 105 ms 6348 KB Output is correct
17 Correct 125 ms 7396 KB Output is correct
18 Correct 666 ms 8784 KB Output is correct
19 Correct 162 ms 20312 KB Output is correct
20 Correct 144 ms 21424 KB Output is correct
21 Incorrect 165 ms 22020 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 20864 KB Output is correct
2 Correct 336 ms 24088 KB Output is correct
3 Correct 336 ms 24244 KB Output is correct
4 Correct 353 ms 33796 KB Output is correct
5 Correct 355 ms 24268 KB Output is correct
6 Correct 419 ms 33620 KB Output is correct
7 Correct 418 ms 30380 KB Output is correct
8 Correct 401 ms 30684 KB Output is correct
9 Correct 250 ms 29784 KB Output is correct
10 Correct 391 ms 30320 KB Output is correct
11 Correct 402 ms 29960 KB Output is correct
12 Correct 402 ms 30044 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 326 ms 20900 KB Output is correct
3 Correct 334 ms 23904 KB Output is correct
4 Correct 330 ms 23892 KB Output is correct
5 Incorrect 326 ms 25348 KB Output isn't correct
6 Halted 0 ms 0 KB -