oj.uz

Submission #573006

# Submission time Handle Problem Language Result Execution time Memory
573006 2022-06-05T15:47:26 Z AmirElarbi Event Hopping (BOI22_events) C++14
10 / 100
 176 ms 4428 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e4+7;
const int nax = 1005;
const int nax2 = 200005;
typedef complex<int> Point;
#define X real()
#define Y imag()
int s[nax],e[nax];
vi adj[nax];
vi d;
int main(){
    optimise;
    int n,q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i] >> e[i];
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(e[i] <= e[j] && s[j] <= e[i]) adj[i].pb(j);
        }
    }
    while(q--){
        int s,e;
        cin >> s >> e;
        s--,e--;
        int res = -1;
        if(s == e)
        {
            cout << 0 << endl;
            continue;
        }
        d.assign(n, INF);
        d[s] = 0;
        set<ii> q;
        q.insert({0, s});
        while (!q.empty()) {
            int v = q.begin()->second;
            q.erase(q.begin());
            for (auto edge : adj[v]) {
                int u = edge;
                if (d[v] + 1 < d[u]) {
                    q.erase({d[u], u});
                    d[u] = d[v] + 1;
                    if(u == e) {
                        res = d[u];
                        break;
                    }
                    q.insert({d[u], u});
                }
            }
        }
        if(res == -1) cout << "impossible" << endl;
        else cout << res << endl;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 368 KB Output is correct
5 Correct 6 ms 360 KB Output is correct
6 Correct 16 ms 1108 KB Output is correct
7 Correct 34 ms 1972 KB Output is correct
8 Correct 36 ms 3056 KB Output is correct
9 Correct 176 ms 4308 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 0 ms 340 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 368 KB Output is correct
5 Correct 6 ms 360 KB Output is correct
6 Correct 16 ms 1108 KB Output is correct
7 Correct 34 ms 1972 KB Output is correct
8 Correct 36 ms 3056 KB Output is correct
9 Correct 176 ms 4308 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 8 ms 360 KB Output is correct
13 Correct 6 ms 340 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 18 ms 1204 KB Output is correct
16 Correct 38 ms 2012 KB Output is correct
17 Correct 37 ms 2972 KB Output is correct
18 Correct 166 ms 4428 KB Output is correct
19 Runtime error 1 ms 468 KB Execution killed with signal 11
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 0 ms 340 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 368 KB Output is correct
5 Correct 6 ms 360 KB Output is correct
6 Correct 16 ms 1108 KB Output is correct
7 Correct 34 ms 1972 KB Output is correct
8 Correct 36 ms 3056 KB Output is correct
9 Correct 176 ms 4308 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 16 ms 1108 KB Output is correct
16 Correct 34 ms 2004 KB Output is correct
17 Correct 37 ms 3028 KB Output is correct
18 Correct 169 ms 4308 KB Output is correct
19 Runtime error 1 ms 480 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 1 ms 468 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 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -