Submission #1270205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270205		bhnm	Passport (JOI23_passport)	C++17	100 / 100	643 ms	97332 KiB

passport

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
const int INF = 1e9;

int n,m,x;
int L[MAXN], R[MAXN], nodeId[MAXN];
int distFrom1[5*MAXN], distFromN[5*MAXN], dist[5*MAXN], order[5*MAXN];
int p[5*MAXN];
vector<pair<int,int>> graph[5*MAXN];

void buildSegmentTree(int cur, int l, int r) {
    if (l == r) {
        graph[nodeId[l]].push_back({cur, 0});
        return;
    }
    int mid = (l + r) / 2;
    buildSegmentTree(cur*2, l, mid);
    buildSegmentTree(cur*2+1, mid+1, r);

    graph[cur*2].push_back({cur, 0});
    graph[cur*2+1].push_back({cur, 0});
}
void addEdge(int cur, int l, int r, int ql, int qr, int x) {
    if (ql <= l && r <= qr) {
        graph[cur].push_back({nodeId[x], 1});
        return;
    }
    if (qr < l || ql > r) return;
    int mid = (l + r) / 2;
    addEdge(cur*2, l, mid, ql, qr, x);
    addEdge(cur*2+1, mid+1, r, ql, qr, x);
}

// 0-1 BFS
void bfs(int start, int startVal, bool keepDist) {
    deque<int> dq;
    if (!keepDist) {
        for (int i = 1; i <= 5*n; i++) dist[i] = INF;
    }
    dist[start] = startVal;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (pair<int,int> it : graph[u])
        {
            int v = it.first;
            int w = it.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}
bool cmp(int a,int b)
{
    return dist[a] < dist[b];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> L[i] >> R[i];
        nodeId[i] = 4*n + i;
    }

    buildSegmentTree(1, 1, n);

    for (int i = 1; i <= n; i++) {
        addEdge(1, 1, n, L[i], R[i], i);
    }

    bfs(nodeId[1], 0, false);
    for (int i = 1; i <= 5*n; i++) distFrom1[i] = dist[i];

    bfs(nodeId[n], 0, false);
    for (int i = 1; i <= 5*n; i++) distFromN[i] = dist[i];
    for(int i = 1;i<=4*n;++i)
    {
        dist[i] = INF;
    }
    for(int i = 4*n+1;i<=5*n;++i)
    {
        dist[i] = distFrom1[i] + distFromN[i];
        if(i > 4 * n + 1 && i < 5*n)
        {
            dist[i]--;
        }
        p[i] = i;
    }
    sort(p+1,p+5*n+1,cmp);
    for(int i = 1;i<=5*n;++i)
    {
        bfs(p[i],dist[p[i]],true);
    }
    cin>>m;
    while(m--)
    {
        cin>>x;
        if(dist[nodeId[x]] >= INF)
        {
            cout<<-1<<"\n";
        }
        else
        {
            cout<<dist[nodeId[x]]<<"\n";
        }
    }


}

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