Submission #604467

#	Time	Username	Problem	Language	Result	Execution time	Memory
604467		krit3379	Event Hopping (BOI22_events)	C++17	0 / 100	148 ms	19356 KiB

events

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

struct A{
    int s,e,id;
    bool operator<(const A& o)const{
        if(e!=o.e)return e>o.e;
        return s<o.s;
    }
};

int s[N],e[N],dep[N],nxt[20][N],mi;
vector<int> g[N];
vector<A> edge;

void dfs(int s){
    for(auto x:g[s]){
        dep[x]=dep[s]+1;
        dfs(x);
    }
}

int main(){
    int n,q,i,j,a,b;
    scanf("%d %d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d %d",&s[i],&e[i]);
        edge.push_back({s[i],e[i],i});
    }
    sort(edge.begin(),edge.end());
    mi=1e9;
    for(auto [s,e,id]:edge){
        if(mi<=e)nxt[0][id]=i;
        if(s<mi)mi=s,i=id;
    }
    for(i=1;i<=n;i++)g[nxt[0][i]].push_back(i);
    dfs(0);
    for(i=1;i<20;i++)for(j=1;j<=n;j++)nxt[i][j]=nxt[i-1][nxt[i-1][j]];
    while(q--){
        scanf("%d %d",&a,&b);
        if(s[a]==s[b]&&e[a]==e[b])printf("1\n");
        else if(dep[a]<dep[b])printf("impossible\n");
        else{
            int dif=dep[a]-dep[b];
            for(i=0;i<20;i++)if(dif&(1<<i))a=nxt[i][a];
            if(a==b)printf("%d\n",dif);
            else printf("impossible\n");
        }
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
events.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d",&s[i],&e[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
events.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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