Submission #1126872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126872		Pwo	Passport (JOI23_passport)	C++17	40 / 100	2113 ms	556548 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));
       for (const int u : g[1]) {
			q.push(u); visited[u] = 1, d1[u] = 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));
        for (const int u : g[n]) {
			q.push(u); visited[u] = 1, dn[u] = 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++) {
			int tmp = dist[i] + d1[i] + dn[i];
            ans = min(ans, tmp);
            //if (tmp == ans) cout << i << ' ' << dist[i] << ' ' << d1[i] << ' ' << dn[i] << '\n';
        }
        cout << (ans == 1e9 ? -1 : ans + 1) << '\n';
    }
}

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