제출 #1261223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261223		SzymonKrzywda	Passport (JOI23_passport)	C++20	54 / 100	2099 ms	77912 KiB

passport

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using pii = pair<int, int>;

const int base = 1 << 18;
const int MAXN = 2 * base;

int wygrana = 0;
int n, a, b;
vector<pii> prz;


vector<pair<int, int>> graf2[MAXN];

vector<int> bfs01(int v) {
    deque<pii> kolejka;
    kolejka.push_back({0, v});
    vector<int> wyniki(MAXN, 1e9);

    if (v != wygrana) {
        for (int i = 0; i < n; i++) {
            //cout << prz[i].first << ' ' << prz[i].second << ' ' << v - base << '\n'; 
            if (prz[i].first <= v - base && prz[i].second >= v - base) {
                kolejka.push_back({0, i + base});
                wyniki[i + base] = 0;
            }
        }
    }
    wyniki[v] = 0;
    while (!kolejka.empty()) {
        int v = kolejka.front().second;
        int cost = kolejka.front().first;
        kolejka.pop_front();
        if (wyniki[v] < cost) continue;
    
        for (auto & [s, w] : graf2[v]) {
            if (cost + w < wyniki[s]) {
                wyniki[s] = cost + w;
                if (w == 0) kolejka.push_front({cost + w, s});
                else kolejka.push_back({cost + w, s});
            }
        }
    
        
    }


    return wyniki;
}


void build(int v){
    if (v >= base) return;
    graf2[v * 2].push_back({v, 0});
    graf2[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)) {
            //cout << "DODJAEA: " << idx << ' ' << a << ' ' << b << '\n';
            graf2[a + 1].push_back({idx, 1});
        }
        if (b & 1) {
            //cout << "DODJAEB: " << idx << ' ' << a << ' ' << b << '\n';
            graf2[b - 1].push_back({idx, 1});
        }
        a /= 2;
        b /= 2;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    build(1);

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        a--;
        b--;
        dodaj(i, a, b);
        prz.push_back({a, b});
    }

    vector<int> odl1 = bfs01(base);
    vector<int> odln = bfs01(base + n - 1);
    // for (int i = 0; i < MAXN; i++) {
    //     cout << i << ' ' << odl1[i] << ' ' << odln[i] << '\n';
    //     cout << i << ": ";
    //     for (auto & [s, w] : graf2[i]) cout << s << ' ';
    //     cout << '\n';
    // }
    for (int i = base; i < base + n; i++) {
        graf2[wygrana].push_back({i, odl1[i] + odln[i]});
        //cout << "DODJAE WYGRANA: " << i << ' ' << wygrana << ' ' << odl1[i] << ' ' <<  odln[i] << '\n';
    }

    vector<int> odp = bfs01(wygrana);

    int q, val;
    cin >> q;
    while (q--) {
        cin >> val;
        if (odp[base + val - 1] >= 1e9) cout << -1 << '\n';
        else cout << odp[base + val - 1] + 1 << '\n';
    }

    return 0;
}

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