Submission #797913

#	Time	Username	Problem	Language	Result	Execution time	Memory
797913		azberjibiou	Passport (JOI23_passport)	C++17	100 / 100	651 ms	109372 KiB

passport

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppi pair<pii, pii>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=200006;
const int mxM=10004;
const int MOD=1e9;
const ll INF=1e18;
int N;
int L[mxN], R[mxN];
vector <pii> v[6*mxN];
int dp[mxN];
int dis[6*mxN];
void input()
{
    cin >> N;
    for(int i=1;i<=N;i++)   cin >> L[i] >> R[i];
}
void init(int idx, int s, int e)
{
    if(s==e)
    {
        v[s].emplace_back(N+idx, 0);
        return;
    }
    v[N+2*idx].emplace_back(N+idx, 0);
    v[N+2*idx+1].emplace_back(N+idx, 0);
    int mid=(s+e)/2;
    init(2*idx, s, mid);
    init(2*idx+1, mid+1, e);
}
void make_edge(int idx, int s1, int e1, int s2, int e2, int pos)
{
    if(s2>e1 || s1>e2)  return;
    if(s2<=s1 && e1<=e2)
    {
        v[N+idx].emplace_back(pos, 1);
        return;
    }
    int mid=(s1+e1)/2;
    make_edge(2*idx, s1, mid, s2, e2, pos);
    make_edge(2*idx+1, mid+1, e1, s2, e2, pos);
}
void bfs(int src)
{
    for(int i=1;i<=6*N+1;i++) dis[i]=MOD;
    deque <pii> deq;
    deq.emplace_back(src, 0);
    while(deq.size())
    {
        auto [now, x]=deq.front();
        deq.pop_front();
        if(dis[now]!=MOD)   continue;
        dis[now]=x;
        for(auto [nxt, val] : v[now])   if(dis[nxt]==MOD)
        {
            if(val==0)  deq.emplace_front(nxt, x);
            else    deq.emplace_back(nxt, x+1);
        }
    }
}
void make_graph()
{
    init(1, 1, N);
    for(int i=1;i<=N;i++)   make_edge(1, 1, N, L[i], R[i], i);
    v[6*N+1].emplace_back(5*N+1, 1);
    for(int i=1;i<N;i++)    v[5*N+i].emplace_back(5*N+i+1, 1);

}
void solv_dis()
{
    bfs(N);
    for(int i=1;i<=N;i++)   dp[i]+=dis[i];
    bfs(1);
    for(int i=1;i<=N;i++)   dp[i]+=dis[i];
    for(int i=2;i<N;i++)    dp[i]--;
    for(int i=1;i<=N;i++)
    {
        if(dp[i]<=N)    v[5*N+dp[i]].emplace_back(i, 0);
    }
    bfs(6*N+1);
}
int main()
{
    gibon
    input();
    make_graph();
    solv_dis();
    int T;
    cin >> T;
    while(T--)
    {
        int a;
        cin >> a;
        cout << (dis[a]>=MOD ? -1 : dis[a]) << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46