Submission #896511

#	Time	Username	Problem	Language	Result	Execution time	Memory
896511		karamkallasi	Event Hopping (BOI22_events)	C++14	0 / 100	57 ms	27288 KiB

events

#include <bits/stdc++.h>
#define T ll tt ; cin>>tt ; while(tt--)
#define fast ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define endl '\n'
#define yes void (cout << "YES" << endl)
#define no void (cout << "NO" << endl)
#define pb push_back
#define F first
#define S second
#define ld long double
#define fixed(g) fixed<<setprecision(g)
#define ll long long
using namespace std;
const ll N = 2e6 + 9 ;
const ll oo = 1e18 + 7 ;
ll n , m , x , y , ans , a[N] , b[N] , sz[N] , son[N] , par[N] , dis[N];
bool vis[N] , ff , ok[N];
vector<pair<ll , pair<ll , ll> > >v;
vector<ll>l ;

void init(){
    for(ll i=0 ;i<=n ; i++){
        sz[i] = i ;
        par[i] = i ;
    }
}
ll get(ll x){
    if(x==par[x])return x ;
    return par[x] = get(par[x]) ;
}
void unit(ll x , ll y){
    x = get(x) , y = get(y) ;
    if(x==y)return ;
    if(sz[x]<sz[y])swap(x , y) ;
    sz[x] +=sz[y] ;
    par[y] = x ;
}
void dfs(ll x){
    vis[x]  = 1 ;
    if(vis[son[x]])return ;
    dis[son[x]] = dis[x]+1 ;
    unit(x , son[x]) ;
    dfs(son[x]) ;
}
int main(){
fast
    cin >> n >> m ;
    for(ll i=1 ; i<=n ; i++){
        cin >> a[i] >> b[i]  ;
        v.pb({a[i] , {i , 0}}) ;
        v.pb({b[i] , {i , 1}}) ;
        son[i] = 0 ;
        dis[i] = 0 ;
    }
    sort(v.begin() , v.end()) ;
    for(ll i=0 ; i<2*n ; i++){
        if(v[i].S.S==0){
            l.pb(v[i].S.F) ;
        }
        else{
            son[v[i].S.F] = l.back() ;
            l.pop_back() ;
        }
    }

    init();
    for(ll i=1 ; i<=n ; i++){
        if(!vis[i]){
            dfs(i);
        }
    }
   // for(ll i=1 ; i<=n ; i++)cout<<par[i]<<' ';
   while(m--){
        cin >> x >> y ;
        if(get(x)==get(y)){
            cout<<abs(dis[x] - dis[y]) << endl;
        }
        else cout<<"impossible"<<endl;
   }
    return 0 ;
}

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