Submission #1125141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125141		EfeBabagil	Event Hopping (BOI22_events)	C++20	0 / 100	236 ms	19664 KiB

events

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

vector<int>dsu(1e6);
vector<int> s(1e6,1);
int find(int x)
{
    if(dsu[x]==x)
    return x;
    return dsu[x]=find(dsu[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
    return;
    if(s[x]<s[y])
    swap(x,y);
    dsu[y]=dsu[x];
    s[x]+=s[y];
    
}
int32_t main()
{
    int n,q;
    cin>>n>>q;
    vector<int> dis(n);
    vector<array<int,3>> events(n);
    for(int i=0;i<n;i++)
    {
        int e,s;
        cin>>s>>e;
        events[i]={s,e,i};
        dsu[i]=i;
    }
   
    sort(events.begin(),events.end());
    for(int i=0;i<n-1;i++)
    {
        if((events[i+1][0] <= events[i][1] && events[i][1] <= events[i+1][1])||(
            events[i][0] <= events[i+1][1] && events[i+1][1] <= events[i][1])) 
            {
                merge(events[i][2],events[i+1][2]);
                dis[i+1]=dis[i]+1;
            }
    }
    /*
    for(int i=0;i<n;i++)
    cout<<dis[i]<<" ";
    cout<<endl;*/
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        if(dsu[a]!=dsu[b])
        {
            cout<<"impossible"<<endl;
            continue;
            
        }
        if(a==b){
        cout<<0<<endl;
        continue;
        }
        if((events[b][0] <= events[a][1] && events[a][1] <= events[b][1])||(
                events[a][0] <= events[b][1] && events[b][1] <= events[a][1]))
        cout<<1<<endl;
        else if(dis[b]-dis[a]<0)
        cout<<"impossible"<<endl;
        else
            cout<<(dis[b]-dis[a])<<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