제출 #1246329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246329		adam17	Event Hopping (BOI22_events)	C++20	0 / 100	148 ms	14144 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct dint{
    int a;
    int b;
};

int N, Q, H, hh;
vector<dint> A;
vector<int> R;
vector<int> B;
vector<vector<int>> S;
vector<int> HL;
vector<int> O;
vector<vector<int>> D;

bool comp1(int i, int j) {
    return A[i].b < A[j].b;
}

bool jde(int i, int j) {
    return ((A[B[j]].a <= A[B[i]].b) && (A[B[i]].b <= A[B[j]].b));
}

int main() {
    cin >> N >> Q;
    A.resize(N);
    B.resize(N);
    R.resize(N);
    D.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i].a >> A[i].b;
        B[i] = i;
        R[i] = -1;
        D[i].resize(0);
    }
    sort(B.begin(), B.end());
    for (int j = 0; j < N; j++) {
        int i = j - 1;
        while (jde(i, j)) {
            if (R[i] == -1) {
                R[i] = j;
            }
            i--;
            if (i < 0) {
                goto abcd;
            }
        }
        abcd:;
    }

    hh = 1;
    H = 3;
    while (hh < N) {
        H++;
        hh *= 2;
    }
    S.resize(H);
    for (int h = 0; h < H; h++) {
        S[h].resize(N);
        for (int i = 0; i < N; i++) {
            S[h][i] = ((h == 0) ? R[i] : ((S[h - 1][i] == -1) ? -1 : S[h - 1][S[h - 1][i]]));
        }
    }

    O.resize(0);
    for (int i = 0; i < N; i++) {
        if (R[i] == -1) {
            O.push_back(i);
        } else {
            D[R[i]].push_back(i);
        }
    }
    HL.resize(N);
    while (O.size() > 0) {
        int o = O.back(); O.pop_back();
        HL[o] = ((R[o] == -1) ? 0 : HL[R[o]] + 1);
        for (int d: D[o]) {
            O.push_back(d);
        }
    }

    for (int q = 0; q < Q; q++) {
        int u, v;
        cin >> u >> v; u--; v--;
        // if (HL[u] < HL[v]) {
        //     u ^= v;
        //     v ^= u;
        //     u ^= v;
        // }
        if (HL[u] < HL[v]) {
            cout << "impossible\n";
        } else {
            int result = HL[u] - HL[v];
            hh = 1;
            int h = 0;
            while (HL[u] != HL[v]) {
                if ((HL[u] - HL[v]) % (2 * hh) != 0) {
                    u = S[h][u];
                }
                H++;
                hh *= 2;
            }
            if (u == v) {
                cout << result << endl;
            } else {
                cout << "impossible\n";
            }
        }
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30