Submission #1126840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126840		Pwo	Passport (JOI23_passport)	C++17	0 / 100	2119 ms	488096 KiB

passport

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

int n, q;
pair<int, int> a[200005];
vector<int> g[200005];
bool visited[200005];
int dist[200005], d1[200005], dn[200005];

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        for (int j = a[i].first; j <= a[i].second; j++)
            g[j].push_back(i);
    }
    cin >> q;
    while (q--) {
        int x; cin >> x;
        fill(dist, dist + n + 1, 1e9);
        fill(d1, d1 + n + 1, 1e9);
        fill(dn, dn + n + 1, 1e9);
        
        queue<int> q; q.push(x);
        visited[x] = 1; dist[x] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int i = a[v].first; i <= a[v].second; i++) {
                if (visited[i]) continue;
                visited[i] = 1;
                dist[i] = dist[v] + 1;
                q.push(i);
            }
        }
        
        memset(visited, 0, sizeof(visited));
        q.push(1); visited[1] = 1, d1[1] = 0;
        while (!q.empty()) {
            int v= q.front(); q.pop();
            for (const int u : g[v]) {
                if (visited[u]) continue;
                visited[u] = 1;
                d1[u] = d1[v] + 1;
                q.push(u);
            }
        }
        
        memset(visited, 0, sizeof(visited));
        q.push(n); visited[n] = 1, dn[n] = 0;
        while (!q.empty()) {
            int v= q.front(); q.pop();
            for (const int u : g[v]) {
                if (visited[u]) continue;
                visited[u] = 1;
                dn[u] = dn[v] + 1;
                q.push(u);
            }
        }
        
        int ans = 1e9;
        for (int i = 1; i <= n; i++) {
            ans = min(ans, dist[i] + d1[i] + dn[i] - (i == x && i != 1 && i != n));
            
        }
        cout << (ans == 1e9 ? -1 : ans) << '\n';
    }
}

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