oj.uz

Submission #604467

# Submission time Handle Problem Language Result Execution time Memory
604467 2022-07-25T06:47:17 Z krit3379 Event Hopping (BOI22_events) C++17
0 / 100
 148 ms 19356 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 19292 KB Output is correct
2 Correct 118 ms 19272 KB Output is correct
3 Correct 148 ms 19356 KB Output is correct
4 Correct 71 ms 14416 KB Output is correct
5 Incorrect 147 ms 18240 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -