Submission #1075699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075699		LIF	Event Hopping (BOI22_events)	C++14	10 / 100	1570 ms	4948 KiB

events

#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005];
struct nod
{
    int ll;
    int rr;
    int id;
}node[500005];
bool cmp(nod x,nod y)
{
    return x.ll < y.ll;
}
int dis[500005];
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        nod temp = nod{l[i],r[i],i};
        node[i] = temp;
    }
    sort(node+1,node+n+1,cmp);
    set<pair<int,int> > s;
    while(q--)
    {
        for(int i=1;i<=n;i++)dis[i] = 1e9;
        s.clear();
        int init,target;
        int num = 1;
        cin>>init>>target;
        dis[init] = 0;
        pair<int,int> pp = make_pair(r[init],init);
        s.insert(pp);
        while(s.empty() == false)
        {
            pair<int,int> pp = (*s.begin());
            // cout<<"yeah"<<endl;
            // cout<<pp.first<<" "<<pp.second<<endl;
            s.erase(s.begin());
            for(int i=1;i<=n;i++)
            {
                if(dis[pp.second] + 1 < dis[node[i].id] && node[i].ll <= pp.first && node[i].rr >= pp.first)
                {
                    dis[node[i].id] = dis[pp.second] + 1;
                    pair<int,int> temp = make_pair(node[i].rr,node[i].id);
                    s.insert(temp);
                }
            }
        }
        // for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
        // cout<<endl;
        if(dis[target] != 1e9)cout<<dis[target]<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:31:13: warning: unused variable 'num' [-Wunused-variable]
   31 |         int num = 1;
      |             ^~~

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