oj.uz

Submission #745756

# Submission time Handle Problem Language Result Execution time Memory
745756 2023-05-21T07:22:48 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 99 ms 17460 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> > components;
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;
}

void dfs(int x, int ind) {
    components[ind].push_back(x);
    pos[x] = {ind, components[ind].size()};

    for(int sz : g[x]) dfs(sz, ind);
}

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);
    pos.resize(n+1);
    vector<Event > events;
    for(int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        events.push_back({x, y, i+1});
    }


    sort(events.begin(), events.end());
    vector<int> be(n+1, 0);

    for(int i = 0; i < n-1; i++) {
        if(events[i].e >= events[i+1].s) {
            g[events[i].ind].push_back(events[i+1].ind);
            be[events[i+1].ind]++;
        }
    }

    for(int i = 1; i <= n; i++) {
        if(be[i] == 0) {
            components.push_back({});
            dfs(i, components.size()-1);
        }
    }

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

        if(pos[x].first == pos[y].first && pos[x].second < pos[y].second) cout << pos[y].second - pos[x].second << "\n";
        else cout << "impossible\n";
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17460 KB Output is correct
2 Correct 72 ms 17368 KB Output is correct
3 Correct 81 ms 17404 KB Output is correct
4 Correct 73 ms 14612 KB Output is correct
5 Incorrect 78 ms 15108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -