oj.uz

Submission #1040086

# Submission time Handle Problem Language Result Execution time Memory
1040086 2024-07-31T15:55:39 Z Marco_Escandon Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const string ny[2] = {"No", "Yes"};
#define x first
#define y second
vector<vector<ll>> G(200000);
vector<vector<ll>> v;
ll cmc(ll n,ll ini,ll b)
{
    if(v[ini].size()!=0) return v[ini][b];
    v[ini].assign(n+2, 1e9);
    priority_queue<pair<ll,ll>>q;
    q.push({0,ini});
    while(!q.empty())
    {
        pair<ll,ll> a=q.top();q.pop();
        if(v[ini][a.y]==1e9)
        {
            v[ini][a.y]=-a.x;
            for(auto i:G[a.y])
                if(v[ini][i]==1e9)
                    q.push({a.x-1,i});
        }
    }
    return v[ini][b];
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n,q;
    cin>>n>>q;
    v.resize(n+2);
    vector<pair<ll,ll>> cad;
    vector<pair<ll,ll>> input;input.push_back({0,0});
    for(int i=1; i<=n; i++)
    {
        ll a,b;
        cin>>a>>b;
        input.push_back({a,b});
        cad.push_back({a,i});
        cad.push_back({b,i});
    }
    sort(cad.begin(),cad.end());
    set<ll> s;
    for(int i=0; i<cad.size(); i++)
    {
        vector<ll> temp,temp2;
        ll a=i;
        while(i<cad.size()&&cad[a].x==cad[i].x){
            temp.push_back(cad[i].y);
            i++;
        }
        i--;
        for(auto j:temp)
        {
            if(s.find(j)!=s.end())
                temp2.push_back(j);
            else s.insert(j);
        }
        for(auto j:temp2) for(auto k:s) G[j].push_back(k);
        for(auto j:temp2) if(s.find(j)!=s.end()) s.erase(j);
    }
    for(int i=0; i<q; i++)
    {
        ll a,b;
        cin>>a>>b;
        if(input[a].y>input[b].y){ cout<<"impossible"<<"\n"; continue;}
        a=cmc(n,a,b);
        if(a==1e9) cout<<"impossible"<<"\n";
        else cout<<a<<"\n";
    }
    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0; i<cad.size(); i++)
      |                  ~^~~~~~~~~~~
events.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while(i<cad.size()&&cad[a].x==cad[i].x){
      |               ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 66 ms 17580 KB Output is correct
3 Execution timed out 1557 ms 280616 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5468 KB Output is correct
6 Correct 71 ms 7768 KB Output is correct
7 Correct 511 ms 12492 KB Output is correct
8 Correct 593 ms 19000 KB Output is correct
9 Correct 72 ms 21640 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5468 KB Output is correct
6 Correct 71 ms 7768 KB Output is correct
7 Correct 511 ms 12492 KB Output is correct
8 Correct 593 ms 19000 KB Output is correct
9 Correct 72 ms 21640 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5468 KB Output is correct
14 Correct 3 ms 5468 KB Output is correct
15 Correct 65 ms 7624 KB Output is correct
16 Correct 500 ms 12752 KB Output is correct
17 Correct 597 ms 18812 KB Output is correct
18 Correct 70 ms 22760 KB Output is correct
19 Execution timed out 1577 ms 126156 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 2 ms 5468 KB Output is correct
6 Correct 71 ms 7768 KB Output is correct
7 Correct 511 ms 12492 KB Output is correct
8 Correct 593 ms 19000 KB Output is correct
9 Correct 72 ms 21640 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct
11 Correct 2 ms 5148 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct
14 Correct 4 ms 5468 KB Output is correct
15 Correct 66 ms 7600 KB Output is correct
16 Correct 480 ms 12500 KB Output is correct
17 Correct 632 ms 18804 KB Output is correct
18 Correct 70 ms 21740 KB Output is correct
19 Correct 110 ms 26400 KB Output is correct
20 Correct 224 ms 62124 KB Output is correct
21 Runtime error 872 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17576 KB Output is correct
2 Execution timed out 1581 ms 279760 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 66 ms 17580 KB Output is correct
3 Execution timed out 1557 ms 280616 KB Time limit exceeded
4 Halted 0 ms 0 KB -