Submission #1189106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189106		user149	Event Hopping (BOI22_events)	C++20	0 / 100	1595 ms	4076 KiB

events

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

int s[100005];
int e[100005];

int in_deg[100005];
vector<int> adjlist[100005];

int dist[1005];

int main(){
    int N,Q;
    cin>>N>>Q;
    for(int i=1;i<=N;i++) cin>>s[i]>>e[i];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(s[j]<=e[i] && e[i]<e[j]){
                in_deg[j]=1;
                adjlist[i].push_back(j);
            }
        }
    }
    vector<int> topsort;
    for(int i=1;i<=N;i++) if(in_deg[i]==0) topsort.push_back(i);
    for(int i=0;i<=(int)topsort.size()-1;i++){
        int node=topsort[i];
        for(int j:adjlist[node]){
            in_deg[j]--;
            if(in_deg[j]==0) topsort.push_back(j);
        }
    }

    for(int i=1;i<=Q;i++){
        fill(dist,dist+1005,1e9);
        int a,b;
        cin>>a>>b;
        dist[a]=0;

        for(int node:topsort){
            for(int child:adjlist[node]){
                dist[child]=min(dist[child],dist[node]+1);
            }
        }
        
        if(dist[b]<1e9) cout<<dist[b]<<'\n';
        else cout<<"impossible\n";
    }
}

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