Submission #442471

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
442471	2021-07-07 20:02:38	Aryan_Raina	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1097 ms	7172 KiB

ho_t4

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
#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1e9+7;
const int INF = 1e15+5;
const int MXN = 205, MXM = 50005;
vector<ar<int,2>> g[2][MXN];
int a[MXM], b[MXM], w[MXM], revw[MXM], N, M; 
void dijkstra(int s, int t, int typ, vector<int> &dist, vector<bool> &used) {
    vector<int> prev(N, -1); 
    used.resize(M, false); dist.resize(N, INF);
    priority_queue<ar<int,3>, vector<ar<int,3>>, greater<ar<int,3>>> pq;
    pq.push({0, s, -1});
    while (!pq.empty()) {
        auto [d, u, e] = pq.top(); pq.pop();
        if (dist[u] <= d) continue;
        dist[u] = d; prev[u] = e;
        for (auto [v, i] : g[typ][u]) if (dist[v] > d+w[i])
            pq.push({d+w[i], v, i});
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63