Submission #667038

#	Time	Username	Problem	Language	Result	Execution time	Memory
667038		berr	Event Hopping (BOI22_events)	C++17	0 / 100	82 ms	12140 KiB

events

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+37;
vector<int> adj[N];
int d[N], p[N], vis[N], c[N];
// 1. subtask

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; cin>>n>>q;

    vector<array<int, 3>> a(n);
    for(int i=0; i<n; i++)
    {
        cin>>a[i][0]>>a[i][1];
        a[i][2]=i; p[i]=i;
    }

    sort(a.begin(), a.end());

    for(int i=0; i<n-1; i++)
    {
        if(a[i+1][0]<=a[i][1]&&a[i+1][1]>=a[i][1])
        {
            adj[a[i][2]].push_back(a[i+1][2]);
            c[a[i+1][2]]++; 
        }
    }

    queue<array<int, 3>> qu; 

    for(int i=0; i<n; i++)
    {
        if(c[i]==0)
        {
            qu.push({i, 0, i});
        }
    }

    while(qu.size())
    {
        int v=qu.front()[0], u=qu.front()[1], par=qu.front()[2];
        qu.pop();
        d[v]=u; p[v]=par;

        if(adj[v].size()) qu.push({adj[v][0], u+1, par});
    }

    while(q--)
    {
        int s, e; cin>>s>>e;
        s--; e--;
        if(p[s]!=p[e]||d[e]<d[s]) cout<<"impossible"<<"\n";
        else cout<<d[e]-d[s]<<"\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