Submission #1126873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126873		Pwo	Passport (JOI23_passport)	C++20	40 / 100	2124 ms	547228 KiB

passport

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

int n, w;
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);
    }
	fill(d1, d1 + n + 1, 1e9);
	fill(dn, dn + n + 1, 1e9);
    queue<int> q;
    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);
		}
	}
    cin >> w;
    while (w--) {
        int x; cin >> x;
        fill(dist, dist + n + 1, 1e9);
        
        q.push(x);
        memset(visited, 0, sizeof(visited));
        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);
            }
        }
        
        int ans = 1e9;
        for (int i = 1; i <= n; i++) {
			int tmp = dist[i] + d1[i] + dn[i];
            ans = min(ans, tmp);
        }
        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