oj.uz

Submission #1040150

# Submission time Handle Problem Language Result Execution time Memory
1040150 2024-07-31T17:13:49 Z Marco_Escandon Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 46576 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define x first
#define y second
#pragma optimize("O3")
vector<vector<ll>> G( 5005);
vector<ll> v[5005];
vector<pair<ll,ll>> input;
void cmc(ll n,ll ini)
{
    v[ini].assign(n+1,1e9);
    queue<ll> q;
    q.push(ini);
    v[ini][ini]=0;
    while(!q.empty())
    {
        ll a=q.front();q.pop();
        for(auto i:G[a])
        {
            if(v[ini][i]==1e9)
            {
                v[ini][i]=v[ini][a]+1;
                q.push(i);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n,q;
    cin>>n>>q;
    input.push_back({0,0});
    vector<pair<ll,ll>> cad;
    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=1; i<=n; i++)
        cmc(n,i);
    for(int i=0; i<q; i++)
    {
        ll a,b;
        cin>>a>>b;
        a=v[a][b];
        if(a==1e9) cout<<"impossible"<<"\n";
        else cout<<a<<"\n";
    }
    return 0;
}

Compilation message

events.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize("O3")
      | 
events.cpp: In function 'int main()':
events.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0; i<cad.size(); i++)
      |                  ~^~~~~~~~~~~
events.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while(i<cad.size()&&cad[a].x==cad[i].x){
      |               ~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Runtime error 29 ms 6072 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 7 ms 4700 KB Output is correct
5 Correct 9 ms 4504 KB Output is correct
6 Correct 32 ms 5384 KB Output is correct
7 Correct 92 ms 6228 KB Output is correct
8 Correct 112 ms 7248 KB Output is correct
9 Correct 570 ms 8532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 7 ms 4700 KB Output is correct
5 Correct 9 ms 4504 KB Output is correct
6 Correct 32 ms 5384 KB Output is correct
7 Correct 92 ms 6228 KB Output is correct
8 Correct 112 ms 7248 KB Output is correct
9 Correct 570 ms 8532 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 8 ms 4544 KB Output is correct
13 Correct 6 ms 4676 KB Output is correct
14 Correct 8 ms 4544 KB Output is correct
15 Correct 34 ms 5284 KB Output is correct
16 Correct 94 ms 6224 KB Output is correct
17 Correct 113 ms 7252 KB Output is correct
18 Correct 578 ms 8572 KB Output is correct
19 Execution timed out 1564 ms 46576 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct
4 Correct 7 ms 4700 KB Output is correct
5 Correct 9 ms 4504 KB Output is correct
6 Correct 32 ms 5384 KB Output is correct
7 Correct 92 ms 6228 KB Output is correct
8 Correct 112 ms 7248 KB Output is correct
9 Correct 570 ms 8532 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 12 ms 4596 KB Output is correct
13 Correct 8 ms 4696 KB Output is correct
14 Correct 9 ms 4700 KB Output is correct
15 Correct 32 ms 5436 KB Output is correct
16 Correct 92 ms 6096 KB Output is correct
17 Correct 110 ms 7248 KB Output is correct
18 Correct 596 ms 8532 KB Output is correct
19 Runtime error 27 ms 7352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 6112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Runtime error 29 ms 6072 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -