제출 #1177205

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

events

/*
 *
 * author: AbdAlrhman_Sfar
 *
**/

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

const int N = 1e5 + 5;
const int LOG = 20;

bool cmp(pair<int, int>& l, pair<int, int>& r) {
    return l.second < r.second;
}
vector<int> adj; vector<vector<int>> adj2;
int bl[N][LOG];
vector<int> part; int id = 1;
vector<int> d;
void dfs(int u,int p) {
    int i; part[u] = id;
    for (auto& it : adj2[u]) {
        if (it == p) continue;
        bl[it][0] = u; d[it] = d[u] + 1;
        for (i = 1; i < LOG; ++i) bl[it][i] = bl[bl[i][i - 1]][i - 1];
        dfs(it, u);
    }
}


signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<pair<int, int>> v(n);
    vector<int> in(n, 0);
    adj.resize(n); fill(adj.begin(), adj.end(), -1);
    adj2.resize(n);
    for (auto& it : v) cin >> it.first >> it.second;
    vector<pair<int, int>> a(v);
    sort(a.begin(), a.end(), cmp);
    vector<bool> valid(n, 1);
    if (a[n - 2].second == a[n - 1].second) { 
        adj[n - 1] = (n - 2); in[n - 2] = 1;;
        adj2[n - 2].emplace_back(n - 1); valid[n - 1] = 0;
    } 
    int i, j;
    for (i = n - 2; i >= 0; --i) {
        j = adj[i + 1];
        if (a[i + 1].first <= a[i].second && a[i].second <= a[i + 1].second) {
            adj[i] = (i + 1); in[i + 1] = 1;
            adj2[i + 1].emplace_back(i); valid[i] = 0;
        }
        else if (j != -1 && a[j].first <= a[i].second && a[i].second <= a[j].second) {
            adj[i] = (j); ++in[j];
            adj2[j].emplace_back(i); valid[i] = 0;
        }
    }  part.resize(n); fill(part.begin(), part.end(), -1);
    d.resize(n);
    for (i = 0; i < n; ++i) {
        //if (part[i] != -1) continue;
        //if (adj[i] == -1) continue;
        if (valid[i]) {
            for (j = 0; j < LOG; ++j) bl[i][j] = i;
            d[i] = 1;
            dfs(i, i); ++id; 
        }
    }
    while (q--) {
        int u, v; cin >> u >> v; --u, --v;
        if (part[u] != part[v]) { cout << "impossible\n"; continue; }
        int l = 0, r = 1e5 + 5;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            int u1 = u, v1 = v;
            for (i = 0; i < LOG; ++i) {
                if ((mid >> i) & 1)
                    u1 = bl[u1][i], v1 = bl[v1][i];
            } 
            if (u1 == v1) r = mid;
            else l = mid;
        }
        for (i = 0; i < LOG; ++i) {
            if ((r >> i) & 1)
                u = bl[u][i];
        } 
        if (u == v) cout << r << '\n';
        else cout << "impossible\n";
    }
}

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