Submission #1246487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246487		adam17	Event Hopping (BOI22_events)	C++20	20 / 100	1002 ms	17036 KiB

events

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

struct tint{
    int a;
    int b;
    int c;
};

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

vector<int> ot;
vector<int> ot2;
vector<bool> uzavreno;
vector<vector<int>> sousede;

bool comp1(tint i, tint j) {
    if (i.b == j.b) {
        return i.a < j.a;
    } else {
        return i.b < j.b;
    }
}

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

int main() {
    cin >> N >> Q;
    if ((N <= 1000) && (Q <= 100)) {
        A.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i].a >> A[i].b;
        }

        sousede.resize(N);
        for (int i = 0; i < N; i++) {
            sousede[i].resize(0);
            for (int j = 0; j < N; j++) {
                if (jde(i, j)) {
                    sousede[i].push_back(j);
                }
            }
        }

        for (int q = 0; q < Q; q++) {
            int u, v;
            cin >> u >> v; u--; v--;
            uzavreno.resize(N);
            for (int i = 0; i < N; i++) {
                uzavreno[i] = false;
            }
            vzd = -1;
            ot.resize(0);
            ot2.resize(1);
            ot2[0] = u;
            uzavreno[u] = true;
            while (ot2.size() > 0) {
                ot.resize(ot2.size());
                for (int i = 0; i < ot.size(); i++) {
                    ot[i] = ot2[i];
                }
                ot2.resize(0);
                vzd++;
                while (ot.size()) {
                    int o = ot.back(); ot.pop_back();
                    if (o == v) {
                        cout << vzd << endl;
                        goto hotovo;
                    }
                    for (int s: sousede[o]) if (!(uzavreno[s])) {
                        ot2.push_back(s);
                        uzavreno[s] = true;
                    }
                }
            }
            cout << "impossible\n";
            hotovo:;
        }
    } else {
        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;
            A[i].c = i;
            // B[i] = i;
            R[i] = -1;
            D[i].resize(0);
        }
        sort(A.begin(), A.end(), comp1);
        for (int i = 0; i < N; i++) {
            B[A[i].c] = i;
            // cout << A[i].a << A[i].b << A[i].c << ' ';
        }
        // cout << endl;
        // for (int x: B) {
        //     cout << x << endl;
        // }
        // cout << endl;
        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--; u = B[u]; v = B[v];
            
            // if (HL[u] < HL[v]) {
            //     u ^= v;
            //     v ^= u;
            //     u ^= v;
            // }
            if (HL[u] < HL[v]) {
                if (jde(u, v)) {
                    cout << "1\n";
                } else {
                    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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30