oj.uz

Submission #572933

# Submission time Handle Problem Language Result Execution time Memory
572933 2022-06-05T14:06:57 Z MohamedAliSaidane Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 34612 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;
        vpi v;
        int reach[nax][nax];
        vi adj[nax];
        bool vis[nax];
        void solve()
        {
            cin >> n >> q;
            for(int i = 0; i < n ;i ++)
            {
                int s, e;
                cin >> s >> e;
                v.pb({s,e});
            }
            //sort(all(v));
            for(int i = 0; i < n ;i ++)
            {
                for(int j = 0; j < n; j ++)
                {
                    if(i == j)
                        continue;
                    if(v[i].ss >= v[j].ff && v[i].ss <= v[j].ss)
                        adj[i].pb(j);
                }
            }
            while(q--)
            {
                int s, e;
                cin >> s >> e;
                s--; e--;
                if(!vis[s])
                {
                    queue<pii> q;
                    q.push({s,0});
                    while(!q.empty())
                    {
                        int node = q.front().ff;
                        int d=  q.front().ss;
                        q.pop();
                        reach[s][node] =d;
                        for(auto e: adj[node])
                        {
                            if(reach[s][e] != 0)
                                continue;
                            reach[s][e] = d+ 1;
                            q.push({e,d + 1});
                        }
                    }
                    vis[s] = 1;
                }
                if(e == s)
                    cout << "0\n";
                else if(reach[s][e] == 0)
                    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 1 ms 340 KB Output is correct
2 Execution timed out 1579 ms 1564 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 11 ms 2052 KB Output is correct
7 Correct 27 ms 2872 KB Output is correct
8 Correct 30 ms 3856 KB Output is correct
9 Correct 7 ms 4436 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 11 ms 2052 KB Output is correct
7 Correct 27 ms 2872 KB Output is correct
8 Correct 30 ms 3856 KB Output is correct
9 Correct 7 ms 4436 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 5 ms 1108 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 12 ms 2004 KB Output is correct
16 Correct 26 ms 2868 KB Output is correct
17 Correct 29 ms 3896 KB Output is correct
18 Correct 9 ms 4436 KB Output is correct
19 Execution timed out 1573 ms 34612 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 11 ms 2052 KB Output is correct
7 Correct 27 ms 2872 KB Output is correct
8 Correct 30 ms 3856 KB Output is correct
9 Correct 7 ms 4436 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 6 ms 1108 KB Output is correct
14 Correct 7 ms 1248 KB Output is correct
15 Correct 14 ms 2020 KB Output is correct
16 Correct 26 ms 2856 KB Output is correct
17 Correct 29 ms 3864 KB Output is correct
18 Correct 8 ms 4504 KB Output is correct
19 Execution timed out 1580 ms 1620 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 1589 ms 1620 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 340 KB Output is correct
2 Execution timed out 1579 ms 1564 KB Time limit exceeded
3 Halted 0 ms 0 KB -