oj.uz

Submission #745760

# Submission time Handle Problem Language Result Execution time Memory
745760 2023-05-21T07:25:54 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 80 ms 14316 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 && events[i].e <= events[i+1].e) {
            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 0 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 0 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 0 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 80 ms 14288 KB Output is correct
2 Correct 66 ms 14284 KB Output is correct
3 Correct 63 ms 14316 KB Output is correct
4 Correct 63 ms 11584 KB Output is correct
5 Incorrect 68 ms 11992 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 -