Submission #1317033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317033		rythm_of_knight	Passport (JOI23_passport)	C++17	100 / 100	531 ms	218368 KiB

passport

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
stack <int> D[N];
vector <ar <int, 2>> g[N * 5];
int a[2][N], vis[N * 5], n;

void build(int v = 1, int l = 1, int r = n, int par = 0) {
    if (l == r)
        return g[l].push_back({par, 0}), void();
    if (v != 1)
        g[v + n].push_back({par, 0});
    int m = l + r >> 1;
    build(v << 1, l, m, v + n);
    build(v << 1 | 1, m + 1, r, v + n);
}

int ql, qr, qx, qi;
void update(int v, int l, int r) {
    if (ql <= l && r <= qr)
        return g[l == r ? l : v + n].push_back({qx, 1}), void();
    if (ql > r || l > qr)
        return;
    int m = l + r >> 1;
    update(v << 1, l, m);
    update(v << 1 | 1, m + 1, r);
}
void add(int x, int l, int r) {
    ql = l, qr = r, qx = x;
    update(1, 1, n);
}
void bfs(vector <int> &dis) {
    for (int i = 1; i <= n; i++)
        if (dis[i] <= n)
            D[dis[i]].push(i);
    for (int cur_dis = 0; cur_dis <= n; cur_dis++) {
        while (!D[cur_dis].empty()) {
            int x = D[cur_dis].top(); D[cur_dis].pop();
            for (auto &cur : g[x]) {
                int u = cur[0], cost = cur[1];
                if (dis[u] > dis[x] + cost) {
                    dis[u] = dis[x] + cost;
                    D[dis[u]].push(u);
                }
            }
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[0][i] >> a[1][i];
    build();
    for (int i = 1; i <= n; i++)
        add(i, a[0][i], a[1][i]);
    vector <int> da(n * 5, n + 1); da[1] = 0; bfs(da);
    vector <int> db(n * 5, n + 1); db[n] = 0; bfs(db);
    vector <int> dc(n * 5, n + 1);
    for (int i = 1; i <= n; i++)
        dc[i] = da[i] + db[i] + 1 - (i != n) - (i != 1);
    bfs(dc);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (dc[x] > n)
            dc[x] = -1;
        cout << dc[x] << '\n';
    }
}

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