oj.uz

Submission #877538

# Submission time Handle Problem Language Result Execution time Memory
877538 2023-11-23T09:50:08 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 31016 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int32_t main() {
    setIO();

    int n, q;
    cin >> n >> q;
    vector<pii> v(n+1);

    for(int i=1; i<=n; i++) cin >> v[i].first >> v[i].second;

    vector<vector<int> > graph(n+1);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(i == j) continue;
            if(v[j].first <= v[i].second && v[i].second <= v[j].second)
                graph[i].push_back(j);
        }
    }

    auto bfs = [&](int a, int b) {
        vector<bool> vis(n+1);
        vector<int> dist(n+1, 0);
        queue<int> q;
        vis[a] = 1;
        q.push(a);

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

            if(u == b) return dist[b];

            for(int &v : graph[u]) {
                if(vis[v]) continue;
                dist[v] = dist[u] + 1;
                vis[v] = 1;
                q.push(v);
            }
        }

        return -1;
    };

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1564 ms 6352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 15 ms 1884 KB Output is correct
8 Correct 16 ms 3164 KB Output is correct
9 Correct 48 ms 4444 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 15 ms 1884 KB Output is correct
8 Correct 16 ms 3164 KB Output is correct
9 Correct 48 ms 4444 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 7 ms 1280 KB Output is correct
16 Correct 15 ms 2140 KB Output is correct
17 Correct 16 ms 2964 KB Output is correct
18 Correct 48 ms 4444 KB Output is correct
19 Execution timed out 1556 ms 31016 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 15 ms 1884 KB Output is correct
8 Correct 16 ms 3164 KB Output is correct
9 Correct 48 ms 4444 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 4 ms 600 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 7 ms 1232 KB Output is correct
16 Correct 15 ms 1884 KB Output is correct
17 Correct 16 ms 3164 KB Output is correct
18 Correct 61 ms 4508 KB Output is correct
19 Execution timed out 1536 ms 5784 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 1529 ms 5968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1564 ms 6352 KB Time limit exceeded
3 Halted 0 ms 0 KB -