Submission #1308009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308009		nanaseyuzuki	Passport (JOI23_passport)	C++20	48 / 100	283 ms	103812 KiB

passport

#include <bits/stdc++.h>
// Kazusa_Megumi
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 3e5 + 5, mod = 1e9 + 7, inf = 2e18;

int n, q, d1[mn], dn[mn], d[mn];
vector <pii> st[mn << 2];

int left(int id){ return (id << 1) + n; }
int at(int id) { return id + n; }
int right(int id){ return (id << 1 | 1) + n; }

void build(int id, int l, int r){
	if(l == r){
		st[l].push_back({at(id), 0});
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[left(id)].push_back({at(id), 0});
	st[right(id)].push_back({at(id), 0});
}

void update(int id, int l, int r, int u, int v, int t){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[at(id)].push_back({t, 1});
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, u, v, t);
	update(id << 1 | 1, mid + 1, r, u, v, t);
}

void bfs(int s, int kc[]){
	fill(kc, kc + mn, inf);
	deque <int> dq;
	kc[s] = 0; dq.push_back(s);

	while(dq.size()){
		int u = dq.front();
		dq.pop_front();
		for(auto [v, w] : st[u]){
			if(kc[v] > kc[u] + w){
				kc[v] = kc[u] + w;
				if(w) dq.push_back(v);
				else dq.push_front(v);
			}
		}
	}
}

void dijkstra(){
	fill(d, d + mn, inf);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for(int i = 1; i <= n; i++){
		if(d1[i] != inf && dn[i] != inf){
			d[i] = d1[i] + dn[i] - (i != 1 && i != n);
			pq.push({d[i], i});
		}
	}

	while(pq.size()){
		auto [c, u] = pq.top();
		pq.pop();
		if(c > d[u]) continue;
		for(auto [v, w] : st[u]){
			if(d[v] > d[u] + w){
				d[v] = d[u] + w;
				pq.push({d[v], v});
			}
		}
	}
}

void solve() {
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
    	int l, r; cin >> l >> r;
    	update(1, 1, n, l, r, i);
    }
    bfs(1, d1); bfs(n, dn);
    dijkstra();
    cin >> q;
    while(q--){
    	int x; cin >> x;
    	int res = (d[x] == inf ? -1 : d[x]);
    	cout << res << '\n';
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

passport.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main() {
      | ^~~~
passport.cpp: In function 'int main()':
passport.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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