oj.uz

Submission #1069932

# Submission time Handle Problem Language Result Execution time Memory
1069932 2024-08-22T10:11:52 Z mindiyak Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 33672 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
#include <stack>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<pi>> vvpi;
typedef vector<ld> vd;
typedef vector<long long> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int M = 1e9+7;
void init(string name)
{
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
}
void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}
 
int n,q;
vector<pair<pi,int>> arr;
vvi paths(1e5+5);
 
void solve()
{   
    cin >> n >> q;
    FOR(i,0,n){
        int a,b;cin >> a >> b;
        arr.pb({{b,a},i+1});
    }

    sort(arr.rbegin(),arr.rend());

    FOR(i,0,n){
        FOR(j,0,n){
            if(i == j)continue;
            // cerr << i << " " << j << " " << arr[j].F.F << " " << arr[i].F.S << " " << arr[i].F.F << endl;
            if(arr[i].F.S <= arr[j].F.F && arr[i].F.F >= arr[j].F.F){
                paths[arr[j].S].pb(arr[i].S);
            }
            // else{
            //     if(j>i)break;
            // }
        }
    }

    // FOR(i,1,n+1){
    //     cerr << i << " -> ";
    //     for(int j:paths[i])cerr << j << " ";
    //     cerr << endl;
    // }cerr << endl;

    FOR(i,0,q){
        int a,b;cin >> a >> b;

        vi visited(n+2,0);
        vi dist(n+2,1e9);

        priority_queue<pi> pq;
        pq.push({0,a});
        dist[a] = 0;

        while(!pq.empty()){
            int c = pq.top().S;pq.pop();
            if(visited[c])continue;
            visited[c] = 1;

            for(int d:paths[c]){
                if(dist[d] > dist[c] + 1){
                    dist[d] = dist[c] + 1;
                    pq.push({-dist[d],d});
                }
            }
        }

        // FOR(i,1,n+1){
        //     cerr << dist[i] << " ";
        // }cerr << endl;

        if(dist[b] == 1e9)cout << "impossible" << endl;
        else cout << dist[b] << endl;
    }
}   
 
 
int main()
{
    fastIO();
    // init("test");
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Compilation message

events.cpp: In function 'void init(std::string)':
events.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 8 ms 3676 KB Output is correct
7 Correct 17 ms 4532 KB Output is correct
8 Correct 22 ms 5464 KB Output is correct
9 Correct 81 ms 6924 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 8 ms 3676 KB Output is correct
7 Correct 17 ms 4532 KB Output is correct
8 Correct 22 ms 5464 KB Output is correct
9 Correct 81 ms 6924 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 1 ms 2812 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 4 ms 2880 KB Output is correct
14 Correct 3 ms 2652 KB Output is correct
15 Correct 10 ms 3672 KB Output is correct
16 Correct 18 ms 4624 KB Output is correct
17 Correct 20 ms 5568 KB Output is correct
18 Correct 84 ms 6748 KB Output is correct
19 Execution timed out 1553 ms 33672 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 8 ms 3676 KB Output is correct
7 Correct 17 ms 4532 KB Output is correct
8 Correct 22 ms 5464 KB Output is correct
9 Correct 81 ms 6924 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 4 ms 2648 KB Output is correct
15 Correct 9 ms 3672 KB Output is correct
16 Correct 20 ms 4444 KB Output is correct
17 Correct 19 ms 5464 KB Output is correct
18 Correct 81 ms 6748 KB Output is correct
19 Execution timed out 1550 ms 6340 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1518 ms 4560 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 2652 KB Output is correct
2 Execution timed out 1591 ms 4396 KB Time limit exceeded
3 Halted 0 ms 0 KB -