oj.uz

Submission #1040082

# Submission time Handle Problem Language Result Execution time Memory
1040082 2024-07-31T15:52:40 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);
ll cmc(ll n,ll a,ll b)
{
    vector<ll> v(n+2, 1e9);
    priority_queue<pair<ll,ll>>q;
    q.push({0,a});
    while(!q.empty())
    {
        pair<ll,ll> a=q.top();q.pop();
        if(v[a.y]==1e9)
        {
            v[a.y]=-a.x;
            if(a.y==b) return -a.x;
            for(auto i:G[a.y])
                if(v[i]==1e9)
                    q.push({a.x-1,i});
        }
    }
    return 1e9;
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n,q;
    cin>>n>>q;
    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:46: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]
   46 |     for(int i=0; i<cad.size(); i++)
      |                  ~^~~~~~~~~~~
events.cpp:50: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]
   50 |         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 Execution timed out 1593 ms 14076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 38 ms 7316 KB Output is correct
7 Correct 98 ms 12240 KB Output is correct
8 Correct 57 ms 17716 KB Output is correct
9 Correct 657 ms 28224 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 38 ms 7316 KB Output is correct
7 Correct 98 ms 12240 KB Output is correct
8 Correct 57 ms 17716 KB Output is correct
9 Correct 657 ms 28224 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 5008 KB Output is correct
12 Correct 4 ms 5028 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 39 ms 7320 KB Output is correct
16 Correct 98 ms 12128 KB Output is correct
17 Correct 55 ms 17744 KB Output is correct
18 Correct 691 ms 28408 KB Output is correct
19 Execution timed out 1531 ms 126244 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 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 38 ms 7316 KB Output is correct
7 Correct 98 ms 12240 KB Output is correct
8 Correct 57 ms 17716 KB Output is correct
9 Correct 657 ms 28224 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 38 ms 7308 KB Output is correct
16 Correct 96 ms 12184 KB Output is correct
17 Correct 56 ms 17844 KB Output is correct
18 Correct 671 ms 28732 KB Output is correct
19 Correct 451 ms 14008 KB Output is correct
20 Correct 131 ms 18348 KB Output is correct
21 Runtime error 830 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 Execution timed out 1553 ms 13768 KB Time limit exceeded
2 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 Execution timed out 1593 ms 14076 KB Time limit exceeded
3 Halted 0 ms 0 KB -