oj.uz

Submission #1040081

# Submission time Handle Problem Language Result Execution time Memory
1040081 2024-07-31T15:50:49 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;
        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 2 ms 4952 KB Output is correct
2 Execution timed out 1589 ms 15932 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 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 4 ms 5272 KB Output is correct
4 Correct 2 ms 5280 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 70 ms 7356 KB Output is correct
7 Correct 275 ms 12252 KB Output is correct
8 Correct 251 ms 18148 KB Output is correct
9 Correct 645 ms 28156 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 4 ms 5272 KB Output is correct
4 Correct 2 ms 5280 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 70 ms 7356 KB Output is correct
7 Correct 275 ms 12252 KB Output is correct
8 Correct 251 ms 18148 KB Output is correct
9 Correct 645 ms 28156 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 4 ms 5212 KB Output is correct
13 Correct 2 ms 5224 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 71 ms 7332 KB Output is correct
16 Correct 271 ms 12220 KB Output is correct
17 Correct 256 ms 18576 KB Output is correct
18 Correct 698 ms 29944 KB Output is correct
19 Execution timed out 1564 ms 125716 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 4 ms 5272 KB Output is correct
4 Correct 2 ms 5280 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 70 ms 7356 KB Output is correct
7 Correct 275 ms 12252 KB Output is correct
8 Correct 251 ms 18148 KB Output is correct
9 Correct 645 ms 28156 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct
11 Correct 1 ms 4952 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 68 ms 7324 KB Output is correct
16 Correct 283 ms 12248 KB Output is correct
17 Correct 245 ms 18404 KB Output is correct
18 Correct 732 ms 28644 KB Output is correct
19 Correct 467 ms 15616 KB Output is correct
20 Correct 198 ms 20416 KB Output is correct
21 Runtime error 878 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 1598 ms 16776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Execution timed out 1589 ms 15932 KB Time limit exceeded
3 Halted 0 ms 0 KB -