oj.uz

Submission #572927

# Submission time Handle Problem Language Result Execution time Memory
572927 2022-06-05T13:59:28 Z MohamedAliSaidane Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 128512 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second

        ///#define int ll

        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        const int nax = 5001;
        int n, q;
        indexed_set nid;
        vpi v;
        int reach[nax][nax];
        vi adj[nax];
        void solve()
        {
            memset(reach,-1,sizeof(reach));
            cin >> n >> q;
            for(int i = 0; i < n ;i ++)
            {
                int s, e;
                cin >> s >> e;
                nid.insert(s);
                nid.insert(e);
                v.pb({s,e});
            }
            //sort(all(v));
            for(int i = 0; i < n ;i ++)
            {
                for(int j = 0; j < n; j ++)
                {
                    if(v[i].ss >= v[j].ff && v[i].ss <= v[j].ss)
                        adj[i].pb(j);
                }
            }
            for(int i=  0; i < n; i ++)
            {
                queue<pii> q;
                q.push({i,0});
                while(!q.empty())
                {
                    int node = q.front().ff;
                    int d=  q.front().ss;
                    q.pop();
                    reach[i][node] =d;
                    for(auto e: adj[node])
                    {
                        if(reach[i][e] != -1)
                            continue;
                        reach[i][e] = d+ 1;
                        q.push({e,d + 1});
                    }
                }
            }
            while(q--)
            {
                int s, e;
                cin >> s >> e;
                s--; e--;
                if(reach[s][e] == -1)
                    cout << "impossible\n";
                else
                    cout << reach[s][e] << '\n';
            }
        }

        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt = 1;
            while(tt --)
                solve();
        }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98244 KB Output is correct
2 Execution timed out 1584 ms 104000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98252 KB Output is correct
2 Correct 38 ms 98292 KB Output is correct
3 Correct 55 ms 98392 KB Output is correct
4 Correct 50 ms 98408 KB Output is correct
5 Correct 61 ms 98448 KB Output is correct
6 Correct 84 ms 99176 KB Output is correct
7 Correct 180 ms 99960 KB Output is correct
8 Correct 180 ms 100996 KB Output is correct
9 Correct 846 ms 102348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98252 KB Output is correct
2 Correct 38 ms 98292 KB Output is correct
3 Correct 55 ms 98392 KB Output is correct
4 Correct 50 ms 98408 KB Output is correct
5 Correct 61 ms 98448 KB Output is correct
6 Correct 84 ms 99176 KB Output is correct
7 Correct 180 ms 99960 KB Output is correct
8 Correct 180 ms 100996 KB Output is correct
9 Correct 846 ms 102348 KB Output is correct
10 Correct 37 ms 98220 KB Output is correct
11 Correct 37 ms 98252 KB Output is correct
12 Correct 64 ms 98388 KB Output is correct
13 Correct 61 ms 98392 KB Output is correct
14 Correct 59 ms 98272 KB Output is correct
15 Correct 80 ms 99148 KB Output is correct
16 Correct 164 ms 99932 KB Output is correct
17 Correct 239 ms 100988 KB Output is correct
18 Correct 813 ms 102344 KB Output is correct
19 Execution timed out 1574 ms 128512 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98252 KB Output is correct
2 Correct 38 ms 98292 KB Output is correct
3 Correct 55 ms 98392 KB Output is correct
4 Correct 50 ms 98408 KB Output is correct
5 Correct 61 ms 98448 KB Output is correct
6 Correct 84 ms 99176 KB Output is correct
7 Correct 180 ms 99960 KB Output is correct
8 Correct 180 ms 100996 KB Output is correct
9 Correct 846 ms 102348 KB Output is correct
10 Correct 45 ms 98196 KB Output is correct
11 Correct 38 ms 98208 KB Output is correct
12 Correct 57 ms 98292 KB Output is correct
13 Correct 57 ms 98352 KB Output is correct
14 Correct 57 ms 98352 KB Output is correct
15 Correct 84 ms 99176 KB Output is correct
16 Correct 157 ms 100036 KB Output is correct
17 Correct 180 ms 101088 KB Output is correct
18 Correct 811 ms 102344 KB Output is correct
19 Execution timed out 1582 ms 104004 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 1595 ms 103972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 98244 KB Output is correct
2 Execution timed out 1584 ms 104000 KB Time limit exceeded
3 Halted 0 ms 0 KB -