Submission #879339

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
879339	2023-11-27 07:21:23	willychan	Escape Route (JOI21_escape_route)	C++17	25 / 100	9090 ms	194620 KiB

escape_route

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 "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 5e16
std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
    std::vector<int> V, std::vector<long long> T) {
    vector<vector<pair<int,int> >> side(N);
    for(int i=0; i<M; i++) {
        side[A[i]].push_back({B[i],i});
        side[B[i]].push_back({A[i],i});
    }
    vector<vector<vector<pair<ll,ll> > > > dis(N,vector<vector<pair<ll,ll> >>(N,vector<pair<ll,ll> >(2*M,{inf,inf} )));
    for(int e=0; e<M; e++) {
        int x = A[e];
        int y = B[e];
        vector<ll> disx(N,inf);
        vector<ll> disy(N,inf);
        disx[x]=0;
        disy[y]=0;
        vector<bool> reachx(N);
        vector<bool> reachy(N);
        ll T = C[e]-L[e];
        while(true) {
            pair<ll,int> cur = {inf,-1};
            for(int i=0; i<N; i++) if(!reachx[i]) cur = min(cur, {disx[i],i});
            if(cur.first>=inf) break;
            for(auto g : side[cur.second]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30