Submission #1177247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177247		abdalrhman_sfar	Event Hopping (BOI22_events)	C++20	10 / 100	92 ms	23876 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<pair<int,int>, int>& l, pair<pair<int,int>, int>& r) {
    if (l.first.second == r.first.second) return l.first.first < r.first.first;
    return l.first.second < r.first.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[it][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);
    adj.resize(n); fill(adj.begin(), adj.end(), -1);
    adj2.resize(n);
    for (auto& it : v) cin >> it.first >> it.second; 
    vector<pair<pair<int, int>, int>> a(n);
    int i, j;
    for (i = 0; i < n; ++i) a[i].first = v[i], a[i].second = i;
    sort(a.begin(), a.end(), cmp);
    set<pair<int, int>> st;
    vector<bool> valid(n, 1);
    if (a[n - 2].first.second == a[n - 1].first.second) {
        adj[n - 1] = (n - 2); 
        //adj2[a[n - 2].second].emplace_back(a[n - 1].second); //valid[a[n - 1].second] = 0;
        st.insert({ a[n - 2].second, a[n - 1].second });
    }
    for (i = n - 2; i >= 0; --i) {
        j = adj[i + 1];
        if (a[i + 1].first.first <= a[i].first.second && a[i].first.second <= a[i + 1].first.second) {
            adj[i] = (i + 1);
            adj2[a[i + 1].second].emplace_back(a[i].second); valid[a[i].second] = 0;
        }
        else if (j != -1 && j != i && a[j].first.first <= a[i].first.second && a[i].first.second <= a[j].first.second) {
            adj[i] = (j); 
            adj2[a[j].second].emplace_back(a[i].second); valid[a[i].second] = 0;
        }
        else if ((i - 1) >= 0 && a[i - 1].first.first <= a[i].first.second && a[i].first.second <= a[i - 1].first.second) {
            //cout << '\t' << a[i].first.first << ' ' << a[i].first.second << '\n';
            adj[i] = (i - 1);
            //adj2[a[i - 1].second].emplace_back(a[i].second); valid[a[i].second] = 0;
            st.insert({ a[i].second, a[i - 1].second });
        }
    }  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]) {
            //cout << 1+i << '\n';
            for (j = 0; j < LOG; ++j) bl[i][j] = i;
            d[i] = 1; 
            dfs(i, i); ++id;
        }
        //cout << i+1 << '\n';
        //for (auto& it : adj2[i]) cout << it+1 << ' ';cout  << '\n';
    }
    //for (auto& it : bl[2]) cout << it + 1 << ' '; cout << '\n';
    //for (auto& it : bl[1]) cout << it + 1 << ' '; cout << '\n';
    while (q--) {
        int u, v; cin >> u >> v; --u, --v;
        if (st.count({ u,v })) { cout << "1\n"; continue; }
        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, diff = d[v] - d[u];
        //    for (i = 0; i < LOG; ++i) {
        //        if ((mid >> i) & 1)
        //            u1 = bl[u1][i], v1 = bl[v1][i];
        //    } //cout << mid << ' ' << u1 << ' ' << v1 << '\n';
        //    if (u1 == v1) r = mid;
        //    else l = mid;
        //} 
        int diff = d[u] - d[v];
        for (i = 0; i < LOG; ++i) {
            if ((diff >> i) & 1)
                u = bl[u][i];
        }
        if (u == v) cout << diff << '\n';
        else cout << "impossible\n";
    }
}

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