Submission #66778679

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    int M = 2*N;
    vector<int> A(N+1), B(N+1);
    for(int i=1;i<=N;i++){
        cin >> A[i] >> B[i];
    }

    struct Seg { int l, r, id; };
    vector<Seg> segs;
    segs.reserve(3*N);
    for(int i=1;i<=N;i++){
        int a=A[i], b=B[i];
        if(a < b){
            segs.push_back({a, b, i});
        } else {
            segs.push_back({a, b+M, i});
        }
    }
    int K = segs.size();
    for(int i=0;i<K;i++){
        auto &S = segs[i];
        if(S.r <= M){
            segs.push_back({S.l+M, S.r+M, S.id});
        }
    }

    sort(segs.begin(), segs.end(),
         [&](auto &x, auto &y){
             if(x.l!=y.l) return x.l<y.l;
             return x.r<y.r;
         });

    vector<int> parent(N+1, 0),  
                bestR(N+1, INT_MAX);
    set<pair<int,int>> active;    
    for(auto &S: segs){
        while(!active.empty() && active.begin()->first < S.l)
            active.erase(active.begin());
        auto it = active.lower_bound({S.r, -1});
        if(it != active.end()){
            int pid = it->second;
            if(it->first < bestR[S.id]){
                bestR[S.id] = it->first;
                parent[S.id] = pid;
            }
        }
        active.insert({S.r, S.id});
    }
    vector<vector<int>> adj(N+1);
    for(int i=1;i<=N;i++){
        adj[i].push_back(parent[i]);
        adj[parent[i]].push_back(i);
    }
    vector<int> depth(N+1, -1);
    queue<int>q;
    depth[0] = 0;
    q.push(0);
    int maxDepth = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: adj[u]){
            if(depth[v]==-1){
                depth[v] = depth[u]+1;
                maxDepth = max(maxDepth, depth[v]);
                q.push(v);
            }
        }
    }
    int far = 0;
    for(int i=0;i<=N;i++){
        if(depth[i] > depth[far]) far = i;
    }
    vector<int> dist(N+1, -1);
    dist[far]=0;
    q.push(far);
    int diam = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: adj[u]){
            if(dist[v]==-1){
                dist[v] = dist[u]+1;
                diam = max(diam, dist[v]);
                q.push(v);
            }
        }
    }
    cout << max(maxDepth, diam) << "\n";
    return 0;
}

Submission Info

Judge Result