oj.uz

Submission #745775

# Submission time Handle Problem Language Result Execution time Memory
745775 2023-05-21T07:37:28 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

vector<vector<int> > g;

vector<vector<int> > dist;
vector<pair<int, int>> pos;


struct Event {
    int s,e, ind;
};

bool operator<(Event &a, Event &b) {
    if(a.s == b.s) return a.e < b.e;
    return a.s < b.s;
}

int main() {

/*#ifndef ONLINE_JUDGE
   freopen("../../input.txt", "r", stdin);
   freopen("../../output.txt", "w", stdout);
#endif*/
   InTheNameOfGod;

    int n,q;
    cin >> n >> q;

    g.resize(n+1);
    dist.resize(n+1, vector<int>(n+1, -1));
    vector<Event > v;
    for(int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        v.push_back({x, y, i+1});
    }


    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++)  {
            if(i == j) continue;

            if(v[i].e >= v[j].s && v[i].e <= v[j].e) {
                g[i+1].push_back(j+1);
            }
        }
    }

    for(int i = 1; i <= n; i++)  {
        queue<int> q;
        q.push(i);
        dist[i][i] = 0;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            for(int sz : g[cur]) {
                if(dist[i][sz] != -1) continue;
                dist[i][sz] = dist[i][cur] + 1;
                q.push(sz);
            }
        }
    }

    while(q--)  {
        int x,y;
        cin >> x >> y;

        if(dist[x][y] == -1) cout <<  "impossible\n";
        else cout << dist[x][y] << "\n";
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 299 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 15 ms 4372 KB Output is correct
4 Correct 10 ms 4300 KB Output is correct
5 Correct 15 ms 4308 KB Output is correct
6 Correct 66 ms 5076 KB Output is correct
7 Correct 202 ms 5948 KB Output is correct
8 Correct 198 ms 6992 KB Output is correct
9 Correct 1181 ms 8340 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 15 ms 4372 KB Output is correct
4 Correct 10 ms 4300 KB Output is correct
5 Correct 15 ms 4308 KB Output is correct
6 Correct 66 ms 5076 KB Output is correct
7 Correct 202 ms 5948 KB Output is correct
8 Correct 198 ms 6992 KB Output is correct
9 Correct 1181 ms 8340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 14 ms 4376 KB Output is correct
13 Correct 13 ms 4364 KB Output is correct
14 Correct 15 ms 4344 KB Output is correct
15 Correct 55 ms 5124 KB Output is correct
16 Correct 160 ms 5940 KB Output is correct
17 Correct 213 ms 7116 KB Output is correct
18 Correct 1163 ms 8340 KB Output is correct
19 Execution timed out 1565 ms 128588 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 15 ms 4372 KB Output is correct
4 Correct 10 ms 4300 KB Output is correct
5 Correct 15 ms 4308 KB Output is correct
6 Correct 66 ms 5076 KB Output is correct
7 Correct 202 ms 5948 KB Output is correct
8 Correct 198 ms 6992 KB Output is correct
9 Correct 1181 ms 8340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 14 ms 4368 KB Output is correct
13 Correct 9 ms 4308 KB Output is correct
14 Correct 15 ms 4296 KB Output is correct
15 Correct 58 ms 5136 KB Output is correct
16 Correct 182 ms 5928 KB Output is correct
17 Correct 209 ms 6916 KB Output is correct
18 Correct 1249 ms 8344 KB Output is correct
19 Runtime error 194 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 299 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -