제출 #1171026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171026		Faggi	Event Hopping (BOI22_events)	C++20	10 / 100	1603 ms	253048 KiB

events

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MAXN=1e5+1;

vector<ll>grafo[MAXN];
ll n, t, vis[MAXN];
vector<ll> calc(ll a,vector<ll>&dist)
{
    t++;
    queue<ll>pq;
    dist[a]=0;
    pq.push(a);
    while(pq.size())
    {
        ll nod=pq.front();
        pq.pop();
        if(vis[nod]==t)
            continue;
        vis[nod]=t;
        for(auto k:grafo[nod])
        {
            if(dist[k]>dist[nod]+1)
            {
                dist[k]=dist[nod]+1;
                pq.push(k);
            }
        }
    }
    return dist;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, i, pot=1, a, b, act=-1, l, r, ant=LLONG_MIN, ans, j;
    cin >> n >> q;
    vector<pair<ll,ll>>v;
    for(i=0; i<n; i++)
    {
        cin >> a >> b;
        v.pb({a,b});
    }
    map<ll,vector<ll>>m;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            if(v[j].fr<=v[i].se&&v[j].se>=v[i].se)
                grafo[i].pb(j);
        }
    }
    vector<vector<ll>>prec(n,vector<ll>(n,LLONG_MAX));
    for(i=0; i<n; i++)
        prec[i]=calc(i,prec[i]);
    while(q--)
    {
        cin >> a >> b;
        a--;
        b--;
        if(prec[a][b]!=LLONG_MAX)
            cout << prec[a][b] << '\n';
        else
            cout << "impossible\n";

    }
    return 0;
}

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