제출 #1261225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261225		SzymonKrzywda	Passport (JOI23_passport)	C++20	0 / 100	28 ms	29252 KiB

passport

#pragma GCC optimize("O3,unroll-loops,Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

const int base = 1 << 18;       // >= 2e5
const int MAXN = 2 * base + 5;  // graf segmentowy

int wygrana = 0;
int n;

vector<pair<int,int>> graf[MAXN];
vector<pii> przedzialy;

// globalne tablice do BFS
static int distArr[MAXN];
static int vis_id[MAXN];
int cur_id = 0;

void bfs01(int start) {
    ++cur_id;
    deque<int> dq;
    distArr[start] = 0;
    vis_id[start] = cur_id;
    dq.push_back(start);

    if (start != wygrana) {
        int kraj = start - base;
        for (int i = 0; i < n; i++) {
            if (przedzialy[i].first <= kraj && kraj <= przedzialy[i].second) {
                int v = i + base;
                distArr[v] = 0;
                vis_id[v] = cur_id;
                dq.push_back(v);
            }
        }
    }

    while (!dq.empty()) {
        int v = dq.front();
        dq.pop_front();
        int d = distArr[v];
        for (auto &[u,w] : graf[v]) {
            if (vis_id[u] != cur_id || distArr[u] > d + w) {
                distArr[u] = d + w;
                vis_id[u] = cur_id;
                if (w == 0) dq.push_front(u);
                else dq.push_back(u);
            }
        }
    }
}

void build(int v) {
    if (v >= base) return;
    graf[v*2].push_back({v,0});
    graf[v*2+1].push_back({v,0});
    build(v*2);
    build(v*2+1);
}

void dodaj(int idx, int a, int b) {
    a += base - 1;
    b += base + 1;
    idx += base;
    while (a/2 != b/2) {
        if (!(a & 1)) graf[a+1].push_back({idx,1});
        if (b & 1) graf[b-1].push_back({idx,1});
        a /= 2;
        b /= 2;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    build(1);

    for (int i=0;i<n;i++) {
        int L,R; cin >> L >> R;
        L--; R--;
        dodaj(i,L,R);
        przedzialy.push_back({L,R});
    }

    // BFS z lewej
    bfs01(base);
    vector<int> odl1(n);
    for (int i=0;i<n;i++) odl1[i] = distArr[base+i];

    // BFS z prawej
    bfs01(base+n-1);
    vector<int> odln(n);
    for (int i=0;i<n;i++) odln[i] = distArr[base+i];

    // łączymy do sztucznego wierzchołka
    for (int i=0;i<n;i++) {
        int cost = odl1[i] + odln[i];
        if (cost < (int)1e9) graf[wygrana].push_back({base+i, cost});
    }

    // BFS z "wygrana"
    bfs01(wygrana);

    int Q; cin >> Q;
    while (Q--) {
        int x; cin >> x;
        int ans = distArr[base + x - 1];
        if (vis_id[base+x-1] != cur_id || ans >= (int)1e9) cout << -1 << "\n";
        else cout << ans + 1 << "\n";
    }
}

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