Submission #1186347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186347		qwusha	Event Hopping (BOI22_events)	C++20	10 / 100	563 ms	69488 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;


bool cmp(vector<int> a, vector<int> b) {
    return a[1] < b[1];
}

vector<vector<int>> g;
int curc = 0;
vector<int> col;
vector<int> par;
vector<vector<int>> ups;
vector<int> dist;


void dfs(int v, int di = 0, int p = -1) {
    col[v] = curc;
    dist[v] = di;
    par[v] = v;
    if (p != -1)
        par[v] = p;
    for (auto u : g[v]) {
        if (u != p) {
            dfs(u, di + 1,v);
        }
    }
}

int logn;

int lca(int v, int u) {
    if (dist[u] > dist[v]) {
        swap(v, u);
    }
    for (int i = logn - 1; i>= 0; i--) {
        if (dist[ups[i][v]] >= dist[u])
            v = ups[i][v];
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (ups[i][v] != ups[i][u]) {
            v = ups[i][v];
            u = ups[i][u];
        }
    }
    if (v == u)
        return v;
    return par[v];
}

int n;

int dijkstra(int s, int e) {
    dist.assign(n, inf);
    dist[s] = 0;
    set<pair<int, int>> st = {{0, s}};
    while(!st.empty()) {
        auto pa = *st.begin();
        st.erase(pa);
        int v = pa.se;
        int d = pa.fi;
        for(auto u : g[v]) {
            if (dist[u] > d + 1) {
                st.erase({dist[u], u});
                dist[u] = d + 1;
                st.insert({dist[u], u});
            }
        }
    }
    return dist[e];
}



bool check(vector<vector<int>> s) {
    sort(s.begin(), s.end());
    bool ok = 1;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i][1] >= s[i + 1][1])
            ok = 0;
    }
    return ok;
}



signed main() {
    int  q;
    cin >> n >> q;
    col.resize(n, -1);
    par.resize(n);
    dist.resize(n);
    vector<pair<int, int>> evinit(n);
    set<int> comst;
    map<int, int> nval, inival;
    for (int i = 0; i < n; i++) {
        cin >> evinit[i].fi >> evinit[i].se;
        comst.insert(evinit[i].fi);
        comst.insert(evinit[i].se);
    }
    int cur = 0;
    for (auto el : comst) {
        nval[el] = cur;
        inival[cur] = el;
        cur++;
    }
    vector<vector<int>> eve(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        eve[i][0] = nval[evinit[i].fi];
        eve[i][1] = nval[evinit[i].se];
        eve[i][2] = i;
    }

    if (n <= 1000 && q <= 100) {
        g.resize(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                if (eve[j][0] <= eve[i][1] && eve[i][1] <= eve[j][1]) {
                    g[i].push_back(j);
                }
            }
        }
        for (int qw = 0; qw < q; qw++) {
            int s, e;
            cin >> s >> e;
            s--;
            e--;
            int val = dijkstra(s, e);
            if (val == inf) {
                cout << "impossible" << '\n';
            } else {
                cout << val << '\n';
            }
        }
        return 0;
    }

    vector<int> nind(n);
    vector<int> begs;
    int type = 2;
    if (check(eve)) {
        type = 1;
        sort(eve.begin(), eve.end());
        for (int i = 0; i < n; i++) {
            nind[eve[i][2]] = i;
        }
        g.resize(n);
        for (int i = 0; i < n; i++) {
            int val = eve[i][1];
            int l = i, r = n;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                if (eve[mid][0] <= val) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            if (l == i) {
                begs.push_back(i);
            } else {
                g[i].push_back(l);
                g[l].push_back(i);
            }
        }
    } else {
        sort(eve.begin(), eve.end(), cmp);
        for (int i = 0; i < n; i++) {
            nind[eve[i][2]] = i;
        }
        g.resize(n);
        int p = n - 1;
        int end = eve[n - 1][0];
        begs.push_back(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            if (eve[i][1] >= end) {
                g[i].push_back(p);
                g[p].push_back(i);
            } else {
                begs.push_back(i);
            }
            if (eve[i][0] <= end) {
                p = i;
                end = eve[i][0];
            }
        }
    }

    for (auto el : begs) {
        if (col[el] == -1) {
            dfs(el);
            curc++;
        }
    }
    logn = 1;
    int vallog = 1;
    while (vallog < n) {
        vallog *= 2;
        logn++;
    }
    logn+=3;
    ups.resize(logn, vector<int>(n));
    for (int i = 0; i < n; i++) {
        ups[0][i] = par[i];
    }
    for (int j = 1; j < logn; j++) {
        for (int i = 0; i < n; i++) {
            ups[j][i] = ups[j - 1][ups[j - 1][i]];
        }
    }


    for (int qw = 0; qw < q; qw++) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        s = nind[s];
        e = nind[e];
        if (col[s] != col[e]) {
            cout << "impossible" << '\n';
        } else {
            if (type == 2) {
                int lc = lca(s, e);
                if (lc == e || (eve[e][1] == eve[lc][1])){
                    cout << dist[e] - dist[lc] + (dist[s] - dist[lc]) << '\n';
                } else {
                    cout << "impossible" << '\n';
                }
            } else {
                if (eve[e][0] < eve[s][0]) {
                    cout << "impossible" << '\n';
                }
                int v = s;
                for (int i = logn - 1; i>= 0; i--) {
                    if (eve[ups[i][v]][0] < eve[e][0])
                        v = ups[i][v];
                }
                if (eve[v][0] < eve[e][0])
                    v = par[v];
                cout << dist[s] - dist[v] << '\n';
            }

        }
    }
}

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