oj.uz

Submission #953009

# Submission time Handle Problem Language Result Execution time Memory
953009 2024-03-25T10:08:58 Z lovrot Passport (JOI23_passport) C++17
100 / 100
 1700 ms 127568 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 66088 KB Output is correct
2 Correct 441 ms 66092 KB Output is correct
3 Correct 434 ms 65932 KB Output is correct
4 Correct 1602 ms 117464 KB Output is correct
5 Correct 1146 ms 98552 KB Output is correct
6 Correct 1055 ms 94432 KB Output is correct
7 Correct 1076 ms 108288 KB Output is correct
8 Correct 806 ms 105100 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 66216 KB Output is correct
2 Correct 434 ms 66092 KB Output is correct
3 Correct 465 ms 66064 KB Output is correct
4 Correct 444 ms 65860 KB Output is correct
5 Correct 433 ms 66088 KB Output is correct
6 Correct 444 ms 66092 KB Output is correct
7 Correct 431 ms 65996 KB Output is correct
8 Correct 432 ms 66092 KB Output is correct
9 Correct 445 ms 65884 KB Output is correct
10 Correct 431 ms 66320 KB Output is correct
11 Correct 432 ms 66132 KB Output is correct
12 Correct 443 ms 66080 KB Output is correct
13 Correct 452 ms 66204 KB Output is correct
14 Correct 453 ms 65904 KB Output is correct
15 Correct 439 ms 66128 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 66216 KB Output is correct
2 Correct 434 ms 66092 KB Output is correct
3 Correct 465 ms 66064 KB Output is correct
4 Correct 444 ms 65860 KB Output is correct
5 Correct 433 ms 66088 KB Output is correct
6 Correct 444 ms 66092 KB Output is correct
7 Correct 431 ms 65996 KB Output is correct
8 Correct 432 ms 66092 KB Output is correct
9 Correct 445 ms 65884 KB Output is correct
10 Correct 431 ms 66320 KB Output is correct
11 Correct 432 ms 66132 KB Output is correct
12 Correct 443 ms 66080 KB Output is correct
13 Correct 452 ms 66204 KB Output is correct
14 Correct 453 ms 65904 KB Output is correct
15 Correct 439 ms 66128 KB Output is correct
16 Correct 489 ms 66536 KB Output is correct
17 Correct 478 ms 66384 KB Output is correct
18 Correct 477 ms 66616 KB Output is correct
19 Correct 469 ms 66596 KB Output is correct
20 Correct 478 ms 66360 KB Output is correct
21 Correct 461 ms 66456 KB Output is correct
22 Correct 452 ms 66616 KB Output is correct
23 Correct 477 ms 66468 KB Output is correct
24 Correct 471 ms 66556 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 66216 KB Output is correct
2 Correct 434 ms 66092 KB Output is correct
3 Correct 465 ms 66064 KB Output is correct
4 Correct 444 ms 65860 KB Output is correct
5 Correct 433 ms 66088 KB Output is correct
6 Correct 444 ms 66092 KB Output is correct
7 Correct 431 ms 65996 KB Output is correct
8 Correct 432 ms 66092 KB Output is correct
9 Correct 445 ms 65884 KB Output is correct
10 Correct 431 ms 66320 KB Output is correct
11 Correct 432 ms 66132 KB Output is correct
12 Correct 443 ms 66080 KB Output is correct
13 Correct 452 ms 66204 KB Output is correct
14 Correct 453 ms 65904 KB Output is correct
15 Correct 439 ms 66128 KB Output is correct
16 Correct 489 ms 66536 KB Output is correct
17 Correct 478 ms 66384 KB Output is correct
18 Correct 477 ms 66616 KB Output is correct
19 Correct 469 ms 66596 KB Output is correct
20 Correct 478 ms 66360 KB Output is correct
21 Correct 461 ms 66456 KB Output is correct
22 Correct 452 ms 66616 KB Output is correct
23 Correct 477 ms 66468 KB Output is correct
24 Correct 471 ms 66556 KB Output is correct
25 Correct 439 ms 66072 KB Output is correct
26 Correct 463 ms 66152 KB Output is correct
27 Correct 457 ms 66464 KB Output is correct
28 Correct 469 ms 66436 KB Output is correct
29 Correct 496 ms 66376 KB Output is correct
30 Correct 495 ms 66388 KB Output is correct
31 Correct 488 ms 66480 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 66088 KB Output is correct
2 Correct 441 ms 66092 KB Output is correct
3 Correct 434 ms 65932 KB Output is correct
4 Correct 1602 ms 117464 KB Output is correct
5 Correct 1146 ms 98552 KB Output is correct
6 Correct 1055 ms 94432 KB Output is correct
7 Correct 1076 ms 108288 KB Output is correct
8 Correct 806 ms 105100 KB Output is correct
9 Correct 447 ms 66216 KB Output is correct
10 Correct 434 ms 66092 KB Output is correct
11 Correct 465 ms 66064 KB Output is correct
12 Correct 444 ms 65860 KB Output is correct
13 Correct 433 ms 66088 KB Output is correct
14 Correct 444 ms 66092 KB Output is correct
15 Correct 431 ms 65996 KB Output is correct
16 Correct 432 ms 66092 KB Output is correct
17 Correct 445 ms 65884 KB Output is correct
18 Correct 431 ms 66320 KB Output is correct
19 Correct 432 ms 66132 KB Output is correct
20 Correct 443 ms 66080 KB Output is correct
21 Correct 452 ms 66204 KB Output is correct
22 Correct 453 ms 65904 KB Output is correct
23 Correct 439 ms 66128 KB Output is correct
24 Correct 489 ms 66536 KB Output is correct
25 Correct 478 ms 66384 KB Output is correct
26 Correct 477 ms 66616 KB Output is correct
27 Correct 469 ms 66596 KB Output is correct
28 Correct 478 ms 66360 KB Output is correct
29 Correct 461 ms 66456 KB Output is correct
30 Correct 452 ms 66616 KB Output is correct
31 Correct 477 ms 66468 KB Output is correct
32 Correct 471 ms 66556 KB Output is correct
33 Correct 439 ms 66072 KB Output is correct
34 Correct 463 ms 66152 KB Output is correct
35 Correct 457 ms 66464 KB Output is correct
36 Correct 469 ms 66436 KB Output is correct
37 Correct 496 ms 66376 KB Output is correct
38 Correct 495 ms 66388 KB Output is correct
39 Correct 488 ms 66480 KB Output is correct
40 Correct 1700 ms 117888 KB Output is correct
41 Correct 1241 ms 98980 KB Output is correct
42 Correct 1334 ms 127568 KB Output is correct
43 Correct 1250 ms 127200 KB Output is correct
44 Correct 1101 ms 94580 KB Output is correct
45 Correct 1090 ms 102476 KB Output is correct
46 Correct 765 ms 79404 KB Output is correct
47 Correct 1321 ms 107576 KB Output is correct
48 Correct 1089 ms 110612 KB Output is correct