oj.uz

Submission #971971

# Submission time Handle Problem Language Result Execution time Memory
971971 2024-04-29T15:37:05 Z idas Event Hopping (BOI22_events) C++11
10 / 100
 1500 ms 130516 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) int((x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int INF=1e9;

const int N=5010;
int n, q, s[N], e[N], d[N][N];
bool same[N][N];
vi ad[N];

int main()
{
    FAST_IO;
    cin >> n >> q;
    FOR(i, 0, n)
    {
        cin >> s[i] >> e[i];
    }

    FOR(i, 0, n)
    {
        FOR(j, 0, n)
        {
            if(i==j) continue;
            if(s[j]<=e[i] && e[i]<=e[j]){
                ad[i].pb(j);
                if(e[i]==e[j]) same[i][j]=true;
//                cout << i << " -> " << j << '\n';
            }
        }
    }

    FOR(i, 0, n) FOR(j, 0, n) if(i!=j) d[i][j]=-1;

    FOR(i, 0, n)
    {
        queue<int> q; q.push(i);
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(auto x : ad[u]){
                if(d[i][x]==-1){
                    d[i][x]=d[i][u]+1;
                    if(!same[u][x]) q.push(x);
                }
            }
        }
    }

    while(q--){
        int a, b; cin >> a >> b; --a; --b;
        if(d[a][b]==-1){
            cout << "impossible\n";
        }
        else{
            cout << d[a][b] << '\n';
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Runtime error 4 ms 860 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 1 ms 2396 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 15 ms 23132 KB Output is correct
4 Correct 11 ms 23132 KB Output is correct
5 Correct 14 ms 23140 KB Output is correct
6 Correct 31 ms 30180 KB Output is correct
7 Correct 136 ms 24668 KB Output is correct
8 Correct 148 ms 25828 KB Output is correct
9 Correct 14 ms 33372 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 15 ms 23132 KB Output is correct
4 Correct 11 ms 23132 KB Output is correct
5 Correct 14 ms 23140 KB Output is correct
6 Correct 31 ms 30180 KB Output is correct
7 Correct 136 ms 24668 KB Output is correct
8 Correct 148 ms 25828 KB Output is correct
9 Correct 14 ms 33372 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 13 ms 23132 KB Output is correct
13 Correct 10 ms 23388 KB Output is correct
14 Correct 15 ms 23216 KB Output is correct
15 Correct 32 ms 30044 KB Output is correct
16 Correct 122 ms 24784 KB Output is correct
17 Correct 141 ms 25692 KB Output is correct
18 Correct 15 ms 33368 KB Output is correct
19 Execution timed out 1575 ms 130516 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 2396 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 15 ms 23132 KB Output is correct
4 Correct 11 ms 23132 KB Output is correct
5 Correct 14 ms 23140 KB Output is correct
6 Correct 31 ms 30180 KB Output is correct
7 Correct 136 ms 24668 KB Output is correct
8 Correct 148 ms 25828 KB Output is correct
9 Correct 14 ms 33372 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 13 ms 23132 KB Output is correct
13 Correct 10 ms 23132 KB Output is correct
14 Correct 16 ms 23132 KB Output is correct
15 Correct 29 ms 30184 KB Output is correct
16 Correct 119 ms 24776 KB Output is correct
17 Correct 144 ms 25692 KB Output is correct
18 Correct 14 ms 33372 KB Output is correct
19 Runtime error 4 ms 860 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 4 ms 860 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 1 ms 4444 KB Output is correct
2 Runtime error 4 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -