oj.uz

Submission #952802

# Submission time Handle Problem Language Result Execution time Memory
952802 2024-03-24T21:52:15 Z lovrot Passport (JOI23_passport) C++17
22 / 100
 1769 ms 145108 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;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int LOG = 18;
const int N = 1 << LOG;
const ll OO = 1e18;

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<ll> dijkstra(vector<pil> S) {
		vector<ll> D(n, OO);
		set<pli> ST;

		for(int i = 0; i < n; ++i) ST.insert({D[i], i});
		for(pil 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<ll> D1 = G.dijkstra({{N, 0}}); 
	vector<ll> DN = G.dijkstra({{N + n - 1, 0}});
	
	vector<pil> S;
	for(int i = N; i < 2 * N + n; ++i) S.PB({i, D1[i] + DN[i]});

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

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 86656 KB Output is correct
2 Correct 517 ms 86356 KB Output is correct
3 Correct 501 ms 86568 KB Output is correct
4 Correct 1769 ms 145108 KB Output is correct
5 Correct 1377 ms 125876 KB Output is correct
6 Correct 1323 ms 121848 KB Output is correct
7 Correct 1271 ms 135672 KB Output is correct
8 Correct 950 ms 130992 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 86608 KB Output is correct
2 Correct 534 ms 86612 KB Output is correct
3 Correct 509 ms 86608 KB Output is correct
4 Correct 535 ms 86608 KB Output is correct
5 Correct 561 ms 86564 KB Output is correct
6 Correct 542 ms 86816 KB Output is correct
7 Correct 531 ms 86612 KB Output is correct
8 Correct 510 ms 86420 KB Output is correct
9 Correct 493 ms 86864 KB Output is correct
10 Correct 503 ms 86516 KB Output is correct
11 Correct 487 ms 86552 KB Output is correct
12 Correct 485 ms 86600 KB Output is correct
13 Correct 494 ms 86612 KB Output is correct
14 Correct 493 ms 86612 KB Output is correct
15 Correct 486 ms 86616 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 86608 KB Output is correct
2 Correct 534 ms 86612 KB Output is correct
3 Correct 509 ms 86608 KB Output is correct
4 Correct 535 ms 86608 KB Output is correct
5 Correct 561 ms 86564 KB Output is correct
6 Correct 542 ms 86816 KB Output is correct
7 Correct 531 ms 86612 KB Output is correct
8 Correct 510 ms 86420 KB Output is correct
9 Correct 493 ms 86864 KB Output is correct
10 Correct 503 ms 86516 KB Output is correct
11 Correct 487 ms 86552 KB Output is correct
12 Correct 485 ms 86600 KB Output is correct
13 Correct 494 ms 86612 KB Output is correct
14 Correct 493 ms 86612 KB Output is correct
15 Correct 486 ms 86616 KB Output is correct
16 Correct 487 ms 86920 KB Output is correct
17 Correct 504 ms 86948 KB Output is correct
18 Correct 527 ms 87412 KB Output is correct
19 Correct 527 ms 87068 KB Output is correct
20 Correct 508 ms 87248 KB Output is correct
21 Correct 503 ms 87068 KB Output is correct
22 Incorrect 484 ms 86972 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 86608 KB Output is correct
2 Correct 534 ms 86612 KB Output is correct
3 Correct 509 ms 86608 KB Output is correct
4 Correct 535 ms 86608 KB Output is correct
5 Correct 561 ms 86564 KB Output is correct
6 Correct 542 ms 86816 KB Output is correct
7 Correct 531 ms 86612 KB Output is correct
8 Correct 510 ms 86420 KB Output is correct
9 Correct 493 ms 86864 KB Output is correct
10 Correct 503 ms 86516 KB Output is correct
11 Correct 487 ms 86552 KB Output is correct
12 Correct 485 ms 86600 KB Output is correct
13 Correct 494 ms 86612 KB Output is correct
14 Correct 493 ms 86612 KB Output is correct
15 Correct 486 ms 86616 KB Output is correct
16 Correct 487 ms 86920 KB Output is correct
17 Correct 504 ms 86948 KB Output is correct
18 Correct 527 ms 87412 KB Output is correct
19 Correct 527 ms 87068 KB Output is correct
20 Correct 508 ms 87248 KB Output is correct
21 Correct 503 ms 87068 KB Output is correct
22 Incorrect 484 ms 86972 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 86656 KB Output is correct
2 Correct 517 ms 86356 KB Output is correct
3 Correct 501 ms 86568 KB Output is correct
4 Correct 1769 ms 145108 KB Output is correct
5 Correct 1377 ms 125876 KB Output is correct
6 Correct 1323 ms 121848 KB Output is correct
7 Correct 1271 ms 135672 KB Output is correct
8 Correct 950 ms 130992 KB Output is correct
9 Correct 509 ms 86608 KB Output is correct
10 Correct 534 ms 86612 KB Output is correct
11 Correct 509 ms 86608 KB Output is correct
12 Correct 535 ms 86608 KB Output is correct
13 Correct 561 ms 86564 KB Output is correct
14 Correct 542 ms 86816 KB Output is correct
15 Correct 531 ms 86612 KB Output is correct
16 Correct 510 ms 86420 KB Output is correct
17 Correct 493 ms 86864 KB Output is correct
18 Correct 503 ms 86516 KB Output is correct
19 Correct 487 ms 86552 KB Output is correct
20 Correct 485 ms 86600 KB Output is correct
21 Correct 494 ms 86612 KB Output is correct
22 Correct 493 ms 86612 KB Output is correct
23 Correct 486 ms 86616 KB Output is correct
24 Correct 487 ms 86920 KB Output is correct
25 Correct 504 ms 86948 KB Output is correct
26 Correct 527 ms 87412 KB Output is correct
27 Correct 527 ms 87068 KB Output is correct
28 Correct 508 ms 87248 KB Output is correct
29 Correct 503 ms 87068 KB Output is correct
30 Incorrect 484 ms 86972 KB Output isn't correct
31 Halted 0 ms 0 KB -