Submission #1242934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242934		Hamed_Ghaffari	Passport (JOI23_passport)	C++20	48 / 100	44 ms	20548 KiB

passport

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

const int MXN = 2505, inf=1e7;

int n, L[MXN], R[MXN];
vector<int> g[MXN];

int dis[2][MXN], val[MXN];

void bfs(int id, int v) {
    fill(dis[id]+1, dis[id]+n+1, inf);
    queue<int> q;
    dis[id][v] = 0;
    q.push(v);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : g[v])
            if(dis[id][u]>dis[id][v]+1)
                dis[id][u] = dis[id][v]+1,
                q.push(u);
    }
}

int D[MXN];

void SP() {
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 1);
    sort(vec.begin(), vec.end(), [&](int u, int v) {
        return val[u] > val[v];
    });
    fill(D+1, D+n+1, inf);
    queue<int> q;
    while(!q.empty() || !vec.empty()) {
        if(q.empty())
            while(!vec.empty()) {
                int dd = val[vec.back()];
                if(dd<D[vec.back()]) {
                    D[vec.back()] = dd;
                    q.push(vec.back());
                    vec.pop_back();
                    break;
                }
                vec.pop_back();
            }
        if(q.empty()) break;
        while(!vec.empty()) {
            int dd = val[vec.back()];
            if(dd<D[vec.back()] && dd<=D[q.front()]+1) {
                D[vec.back()] = dd;
                q.push(vec.back());
                vec.pop_back();
            }
            else break;
        }
        int v = q.front();
        q.pop();
        for(int u : g[v])
            if(D[u]>D[v]+1)
                D[u] = D[v]+1,
                q.push(u);
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    assert(n<=2500);
    for(int i=1; i<=n; i++) {
        cin >> L[i] >> R[i];
        for(int j=L[i]; j<=R[i]; j++)
            g[j].push_back(i);
    }
    bfs(0, 1);
    bfs(1, n);
    for(int i=1; i<=n; i++) {
        int mn0=inf, mn1=inf;
        for(int j=L[i]; j<=R[i]; j++)
            mn0 = min(mn0, dis[0][j]),
            mn1 = min(mn1, dis[1][j]);
        val[i] = mn0+mn1+1;
    }
    SP();
    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        cout << (D[x]>=inf ? -1 : D[x]) << '\n';
    }
    return 0;
}

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