Submission #953009

#	Time	Username	Problem	Language	Result	Execution time	Memory
953009		lovrot	Passport (JOI23_passport)	C++17	100 / 100	1700 ms	127568 KiB

passport

#include <cstdio> 
#include <vector> 
#include <algorithm> 
#include <set> 

#define X first
#define Y second
#define PB push_back
#define MP make_pair

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 18;
const int N = 1 << LOG;
const int OO = 1e8;

struct graph {
	int n;
	vector<vector<pii>> G; 

	graph() {}
	
	void resize(int size) {
		n = size;
		G.resize(n);
	}

	void add(int u, int v, int w) {
		G[v].PB({u, w});
	}

	vector<int> dijkstra(vector<pii> S) {
		vector<int> D(n, OO);
		set<pii> ST;

		for(int i = 0; i < n; ++i) ST.insert({D[i], i});
		for(pii p : S) {
			ST.erase({D[p.X], p.X});
			D[p.X] = p.Y;
			ST.insert({D[p.X], p.X});
		}

		while(!ST.empty()) {
			int u = (*ST.begin()).Y;
			ST.erase({D[u], u});
			for(pii e : G[u])
				if(D[e.X] > D[u] + e.Y) {
					ST.erase({D[e.X], e.X});
					D[e.X] = D[u] + e.Y;
					ST.insert({D[e.X], e.X});
				}
		}
		return D;
	}
};

graph G;

void spoji(int v, int l, int r, int u = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l) return;
	if(l <= lo && hi <= r) {
		G.add(v, u, 0);
		return;
	}
	int mi = (lo + hi) / 2;
	spoji(v, l, r, 2 * u, lo, mi);
	spoji(v, l, r, 2 * u + 1, mi, hi);
}

int n;

int main() {
	scanf("%d", &n); 

	G.resize(2 * N + n); 

	for(int i = 1; i < N; ++i) {
		G.add(i, 2 * i, 0);
		G.add(i, 2 * i + 1, 0); 
	}

	for(int i = 0; i < n; ++i) {
		int l, r;
		scanf("%d%d", &l, &r); --l; --r;

		G.add(N + i, 2 * N + i, 1); 
		spoji(2 * N + i, l, r + 1);
	}

	vector<int> D1 = G.dijkstra({{N, 0}}); 
	vector<int> DN = G.dijkstra({{N + n - 1, 0}});
	
	vector<pii> S;
	for(int i = N; i < 2 * N + n; ++i) S.PB({i, D1[i] + DN[i]});

	vector<int> ANS = G.dijkstra(S);
	
	int q; scanf("%d", &q); 
	for(; q--; ) {
		int u; scanf("%d", &u); --u;
		printf("%d\n", ANS[N + u] >= OO ? -1 : ANS[N + u]);
	}
	return 0;
}
	

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d", &l, &r); --l; --r;
      |   ~~~~~^~~~~~~~~~~~~~~~
passport.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
passport.cpp:103:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   int u; scanf("%d", &u); --u;
      |          ~~~~~^~~~~~~~~~

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