Submission #714329

#	Time	Username	Problem	Language	Result	Execution time	Memory
714329		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1585 ms	384820 KiB

events

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;
vector<int> adj[100001];
int n;

int bfs(int s, int f)
{
    vector<int> dist(100001, -1);
    queue<int> q;
    q.push(s);
    dist[s] = 0;

    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        for (int i = 0; i < adj[x].size(); i++)
        {
            if (dist[adj[x][i]] == -1)
            {
                dist[adj[x][i]] = dist[x] + 1;
                q.push(adj[x][i]);
            }
        }
    }

    return dist[f];
}
int main()
{
    int q;
    cin >> n >> q;
    set<int> ts;
    vector<pii> v;
    vector<pair<int, pii>> sorted;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        ts.insert(a);
        ts.insert(b);

        v.pb(mpr(a, b));
        sorted.pb(mpr(a, mpr(b, i)));
    }

    cout << endl;
    sort(all(sorted));
    unordered_set<int> on;

    int ind = 0;

    for (int i : ts)
    {
        while (ind < n && sorted[ind].fi <= i)
        {
            if (sorted[ind].fi >= i)
            {
                on.insert(sorted[ind].se.se);
            }
            ind++;
        }


        unordered_set<int> of;
        for (int x : on)
        {

            if (v[x].se == i)
            {
                for (auto j : on)
                {
                    if (x == j) continue;

                    adj[x+1].pb(j+1);
                }
                of.insert(x);
            }
        }

        for (int x : of)
        {
            on.erase(x);
        }
        of.clear();
    }

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        int d = bfs(a, b);
        if (d == -1)
        {
            cout << "impossible\n";
        }
        else
        {
            cout << d << endl;
        }
    }

}

Compilation message (stderr)

events.cpp: In function 'int bfs(int, int)':
events.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < adj[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~

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