Submission #767736

#	Time	Username	Problem	Language	Result	Execution time	Memory
767736		dimash241	Passport (JOI23_passport)	C++17	0 / 100	2 ms	4948 KiB

passport

#include <cstdio>
#include <random>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <chrono>


#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

// вправо, вниз, влево, вверх
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// ход конем
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::system_clock::now().time_since_epoch().count());
int rndInteger (int l, int r) {
    return uniform_int_distribution<int> (l, r)(rnd);
}

const int MOD = (int) 998244353;
const int N = (int) 3e5 + 7;

int n, q;
int l[N], r[N];

int d[4][N];

int vis[N * 4];

void init() {
    memset(vis, 0, sizeof vis);
}

vector<int> g;

void get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if(tr < l || r < tl || vis[v]) return;
    if(tl == tr) {
        g.push_back(tl);
        vis[v] = true;
        return;
    }

    int tm = (tl+tr) >> 1;
    get(l, r, v<<1, tl, tm);
    get(l, r, v<<1|1, tm+1, tr);
    vis[v] = (vis[v<<1] & vis[v<<1|1]);
}

void djk(int id, int st) {
    for (int v = 1; v <= n; ++v) {
        d[id][v] = 1e9;
    }

    d[id][st] = 0;
    set<pair<int,int>> s;
    s.insert({1, st});
    //cout << "start: " << st << endl;
    while(sz(s)) {
        int v = s.begin()->second;
        s.erase(s.begin());

        get(l[v], r[v]);
    //    cout << "djk: " << v << endl;

        for (int to : g) {
    //        cout << "adj: " << to << ' ';
            if(d[id][to] > d[id][v] + 1) {
                s.erase({d[id][to], to});
                d[id][to] = d[id][v] + 1;
                s.insert({d[id][to], to});
            }
        }
    //    cout << '\n';
        g.clear();
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
    }

    init();
    djk(0, 1);


    init();
    djk(1, n);

    init();
    set<pair<int,int>> s;
    for (int v = 1; v <= n; ++v) {
    //    cout << "here: " << v << ' ' << d[0][v] << ' ' << d[1][v] << '\n';

        if(v == 1) {
            d[2][v] = d[0][n];
        } else if(v == n) {
            d[2][v] = d[1][v];
        } else {
            d[2][v] = d[1][v] + d[0][v] - 1;
        }


        if(d[2][v] < 1e9) {
            s.insert({d[2][v], v});
        }
    }

    while(sz(s)) {
        while(sz(s)) {
            int v = s.begin()->second;
            s.erase(s.begin());

            get(l[v], r[v]);

            for (int to : g) {
                if(d[2][to] > d[2][v] + 1) {
                    s.erase({d[2][to], to});
                    d[2][to] = d[2][v] + 1;
                    s.insert({d[2][to], to});
                }
            }
            g.clear();
        }
    }

    cin >> q;
    for(; q; --q) {
        int x;
        cin >> x;

        cout << d[2][x] << '\n';
    }




    return 0;
}

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