Submission #1310412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310412		cansu_mutlu	Event Hopping (BOI22_events)	C++20	10 / 100	1607 ms	250916 KiB

events

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vector<array<int,2>> val(n+1);
    for(int i=1;i<=n;i++)
    cin >> val[i][0] >> val[i][1];
    vector<vector<int>> a(n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(val[i][1]>=val[j][0] && val[i][1]<=val[j][1])
            {
                a[i].push_back(j);
            }
        }
    }
    vector<vector<int>> dist(n+1,vector<int>(n+1,1e18));
    for(int i=1;i<=n;i++)
    {
        priority_queue<array<int,2>> q;
        q.push({0,i});
        dist[i][i] = 0;
        while(q.size())
        {
            int s = q.top()[1];
            q.pop();
            for(int x:a[s])
            {
                if(dist[i][x]==1e18)
                {
                    dist[i][x] = dist[i][s]+1;
                    q.push({-dist[i][x],x});
                }
            }
        }
    }
    while(q--)
    {
        int s,e;
        cin >> s >> e;
        if(dist[s][e]==1e18) cout << "impossible" << endl;
        else cout << dist[s][e] <<endl;
    }
}

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