Submission #727414

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
727414	2023-04-20 15:49:07	model_code	Passport (JOI23_passport)	C++17	100 / 100	531 ms	49224 KiB

passport

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
  FULL-SCORE SOLUTION OF "PASSPORT"
  - The way of implementation is a bit different from official review
    - It does not create graph explicitly
    - It uses Dijkstra's algorithm instead of BFS, but the time complexity does not change in this implementation
  - Time Complexity: O(N log N)
*/
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class state {
public:
  int pos, cost;
  state() : pos(-1), cost(0) {}
  state(int pos_, int cost_) : pos(pos_), cost(cost_) {}
  bool operator<(const state& s) const {
    return cost > s.cost;
  }
};
vector<int> solve(int N, int Q, const vector<int>& L, const vector<int>& R, const vector<int>& X) {
  const int INF = 1012345678;
  // step #1. do segment-tree-like precalculation
  int sz = 1;
  while (sz < N) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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