oj.uz

Submission #748862

# Submission time Handle Problem Language Result Execution time Memory
748862 2023-05-27T05:49:07 Z GrindMachine Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 155212 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];

void solve(int test_case)
{
    int n,q; cin >> n >> q;
    vector<pii> a(n+5);
    rep1(i,n) cin >> a[i].ff >> a[i].ss;

    rep1(i,n){
        rep1(j,n){
            if(i == j) conts;

            auto [si,ei] = a[i];
            auto [sj,ej] = a[j];

            if(sj <= ei and ei <= ej){
                adj[i].pb(j);
            }
        }
    }

    int dis[n+5][n+5];
    memset(dis,-1,sizeof dis);

    rep1(i,n){
        queue<int> qu;
        qu.push(i);
        dis[i][i] = 0;

        while(!qu.empty()){
            int u = qu.front();
            qu.pop();

            trav(v, adj[u]){
                if(dis[i][v] != -1) conts;
                qu.push(v);
                dis[i][v] = dis[i][u] + 1;
            }
        }
    }

    while(q--){
        int u,v; cin >> u >> v;
        int ans = dis[u][v];
        if(ans != -1){
            cout << ans << endl;
        }
        else{
            cout << "impossible" << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1562 ms 5876 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 2644 KB Output is correct
2 Correct 3 ms 2672 KB Output is correct
3 Correct 13 ms 6612 KB Output is correct
4 Correct 9 ms 6612 KB Output is correct
5 Correct 16 ms 6612 KB Output is correct
6 Correct 44 ms 8148 KB Output is correct
7 Correct 105 ms 9888 KB Output is correct
8 Correct 120 ms 11988 KB Output is correct
9 Correct 705 ms 14660 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2672 KB Output is correct
3 Correct 13 ms 6612 KB Output is correct
4 Correct 9 ms 6612 KB Output is correct
5 Correct 16 ms 6612 KB Output is correct
6 Correct 44 ms 8148 KB Output is correct
7 Correct 105 ms 9888 KB Output is correct
8 Correct 120 ms 11988 KB Output is correct
9 Correct 705 ms 14660 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2672 KB Output is correct
12 Correct 12 ms 6668 KB Output is correct
13 Correct 10 ms 6688 KB Output is correct
14 Correct 14 ms 6668 KB Output is correct
15 Correct 45 ms 8236 KB Output is correct
16 Correct 115 ms 9852 KB Output is correct
17 Correct 137 ms 11988 KB Output is correct
18 Correct 666 ms 14664 KB Output is correct
19 Execution timed out 1579 ms 155212 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 2644 KB Output is correct
2 Correct 3 ms 2672 KB Output is correct
3 Correct 13 ms 6612 KB Output is correct
4 Correct 9 ms 6612 KB Output is correct
5 Correct 16 ms 6612 KB Output is correct
6 Correct 44 ms 8148 KB Output is correct
7 Correct 105 ms 9888 KB Output is correct
8 Correct 120 ms 11988 KB Output is correct
9 Correct 705 ms 14660 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 12 ms 6688 KB Output is correct
13 Correct 9 ms 6692 KB Output is correct
14 Correct 15 ms 6672 KB Output is correct
15 Correct 39 ms 8184 KB Output is correct
16 Correct 101 ms 9892 KB Output is correct
17 Correct 132 ms 11988 KB Output is correct
18 Correct 700 ms 14676 KB Output is correct
19 Execution timed out 1564 ms 5828 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 1543 ms 5776 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 2644 KB Output is correct
2 Execution timed out 1562 ms 5876 KB Time limit exceeded
3 Halted 0 ms 0 KB -