oj.uz

Submission #415901

# Submission time Handle Problem Language Result Execution time Memory
415901 2021-06-01T16:56:24 Z koioi.org-koosaga Escape Route (JOI21_escape_route) C++17
100 / 100
 3360 ms 291900 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;

struct edg{
    int pos;
    lint L, C;
};

struct node{
    int i, j; lint max_time;
    bool operator<(const node &n)const{
        return max_time < n.max_time;
    }
};

lint daybreak[96][96];
lint dayfinish[96][96];
lint adj[96][96], dp[96][96];
vector<edg> gph[96];

vector<pi> prec[96][96];
vector<pi> qq[96][96];

lint S;
lint ret[3000005];
lint D1[8100][96], D2[8100][96];

void Do(int n){
	int idx = 0;
    for(int u = 0; u < n; u++){
        for(auto &e : gph[u]){
            int v = e.pos;
            vector<lint> dist1(n, -3e18), dist2(n, 3e18);
            // backward shortest path
            {
                dist1[u] = e.C - e.L;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(-5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = max(ret, pi(dist1[i], i));
                    }
                    if(ret.first < 0) break;
                    int x = ret.second;
                    vis[x] = 1;
                    for(auto &e : gph[x]){
                        if(dist1[e.pos] < dist1[x] - e.L && dist1[x] < e.C){
                            dist1[e.pos] = dist1[x] - e.L;
                        }
                    }
                }
            }
            // forward shortest path
            {
                dist2[v] = e.C;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = min(ret, pi(dist2[i], i));
                    }
                    int x = ret.second;
                    if(ret.first > S) break;
                    vis[x] = 1;
                    for(auto &e : gph[x]){
                        if(dist2[e.pos] > dist2[x] + e.L && dist2[x] + e.L <= e.C){
                            dist2[e.pos] = dist2[x] + e.L;
                        }
                    }
                }
            }
            for(int i = 0; i < n; i++){
            	if(dist1[i] < 0) dist1[i] = -1e18;
            	if(dist2[i] > S) dist2[i] = 1e18;
            	D1[idx][i] = dist1[i];
            	D2[idx][i] = dist2[i];
			}
			idx++;
        }
    }
    for(int i = 0; i < n; i++){
    	vector<tuple<lint, lint, lint>> shit;
    	for(int j = 0; j < n; j++){
    		for(auto &k : qq[i][j]) shit.emplace_back(k.first, k.second, j);
		}
    	vector<int> fuck(idx);
    	iota(all(fuck), 0);
    	sort(all(fuck), [&](int x, int y){
    		return D1[x][i] < D1[y][i];
		});
		sort(all(shit));
		reverse(all(shit));
		vector<lint> ds(n, 1e18);
		for(auto &[T, idx, V] : shit){
			while(sz(fuck) && D1[fuck.back()][i] >= T){
				for(int j = 0; j < n; j++){
					ds[j] = min(ds[j], D2[fuck.back()][j] - D1[fuck.back()][i]);
				}
				fuck.pop_back();
			}
			ret[idx] = min(ret[idx], ds[V]);
		}
	}
}

// wtf just use namespace std and pairs
std::vector<long long> calculate_necessary_time(
        int N, int M, long long Sfuck, 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) {
    S = Sfuck;
    for(int i = 0; i < M; i++){
        gph[A[i]].push_back({B[i], L[i], C[i]});
        gph[B[i]].push_back({A[i], L[i], C[i]});
    }
    {
        priority_queue<node> pq;
        memset(daybreak, 0x3f, sizeof(daybreak));
        auto enq = [&](int s, int e, lint x){
            if(daybreak[s][e] > x){
                daybreak[s][e] = x;
                pq.push({s, e, -x});
            }
        };
        for(int i = 0; i < N; i++){
            enq(i, i, 0);
        }
        while(sz(pq)){
            auto x = pq.top(); pq.pop();
            x.max_time = -x.max_time;
            if(daybreak[x.i][x.j] != x.max_time) continue;
            for(auto &e : gph[x.j]){
                if(x.max_time + e.L <= e.C){
                    enq(x.i, e.pos, x.max_time + e.L);
                }
            }
        }
    }
    {
        priority_queue<node> pq;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                dayfinish[i][j] = -1e18;
            }
        }
        auto enq = [&](int s, int e, lint x){
            if(dayfinish[s][e] < x){
                dayfinish[s][e] = x;
                pq.push({s, e, x});
            }
        };
        for(int i = 0; i < N; i++){
            enq(i, i, S);
        }
        while(sz(pq)){
            auto x = pq.top(); pq.pop();
            if(dayfinish[x.i][x.j] != x.max_time) continue;
            for(auto &e : gph[x.i]){
                lint val = min(x.max_time, e.C) - e.L;
                if(val >= 0) enq(e.pos, x.j, val);
            }
        }
    }
    {
        memset(adj, 0x3f, sizeof(adj));
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(dayfinish[i][j] >= 0) adj[i][j] = 1;
                if(i == j) adj[i][j] = 0;
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < N; k++){
                    adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
                }
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                assert(adj[i][j] <= N);
                dp[i][j] = 1e18;
                for(int k = 0; k < N; k++){
                    dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]);
                }
            }
        }
	}
	fill(ret, ret + Q, 1e18);
	for(int i = 0; i < Q; i++){
		qq[U[i]][V[i]].emplace_back(T[i], i);
	}
	for(int i = 0; i < Q; i++){
		for(int j = 0; j < N; j++){
			if(dayfinish[U[i]][j] >= T[i]){
				ret[i] = min(ret[i], S - T[i] + dp[j][V[i]]);
			}
		}
	}
	Do(N);
	vector<lint> ans(ret, ret + Q);
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65352 KB Output is correct
2 Correct 37 ms 65364 KB Output is correct
3 Correct 81 ms 65360 KB Output is correct
4 Correct 31 ms 65500 KB Output is correct
5 Correct 43 ms 65476 KB Output is correct
6 Correct 34 ms 65376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1489 ms 223344 KB Output is correct
2 Correct 1510 ms 222868 KB Output is correct
3 Correct 1417 ms 254028 KB Output is correct
4 Correct 1463 ms 221128 KB Output is correct
5 Correct 1460 ms 221012 KB Output is correct
6 Correct 35 ms 65396 KB Output is correct
7 Correct 1371 ms 221000 KB Output is correct
8 Correct 1172 ms 218772 KB Output is correct
9 Correct 1404 ms 221012 KB Output is correct
10 Correct 1438 ms 221148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65352 KB Output is correct
2 Correct 37 ms 65364 KB Output is correct
3 Correct 81 ms 65360 KB Output is correct
4 Correct 31 ms 65500 KB Output is correct
5 Correct 43 ms 65476 KB Output is correct
6 Correct 34 ms 65376 KB Output is correct
7 Correct 1489 ms 223344 KB Output is correct
8 Correct 1510 ms 222868 KB Output is correct
9 Correct 1417 ms 254028 KB Output is correct
10 Correct 1463 ms 221128 KB Output is correct
11 Correct 1460 ms 221012 KB Output is correct
12 Correct 35 ms 65396 KB Output is correct
13 Correct 1371 ms 221000 KB Output is correct
14 Correct 1172 ms 218772 KB Output is correct
15 Correct 1404 ms 221012 KB Output is correct
16 Correct 1438 ms 221148 KB Output is correct
17 Correct 1308 ms 197488 KB Output is correct
18 Correct 1283 ms 196368 KB Output is correct
19 Correct 1446 ms 208852 KB Output is correct
20 Correct 1286 ms 196592 KB Output is correct
21 Correct 1460 ms 202984 KB Output is correct
22 Correct 1481 ms 202940 KB Output is correct
23 Correct 1302 ms 190464 KB Output is correct
24 Correct 1211 ms 212756 KB Output is correct
25 Correct 1328 ms 178620 KB Output is correct
26 Correct 1479 ms 202816 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65352 KB Output is correct
2 Correct 37 ms 65364 KB Output is correct
3 Correct 81 ms 65360 KB Output is correct
4 Correct 31 ms 65500 KB Output is correct
5 Correct 43 ms 65476 KB Output is correct
6 Correct 34 ms 65376 KB Output is correct
7 Correct 1489 ms 223344 KB Output is correct
8 Correct 1510 ms 222868 KB Output is correct
9 Correct 1417 ms 254028 KB Output is correct
10 Correct 1463 ms 221128 KB Output is correct
11 Correct 1460 ms 221012 KB Output is correct
12 Correct 35 ms 65396 KB Output is correct
13 Correct 1371 ms 221000 KB Output is correct
14 Correct 1172 ms 218772 KB Output is correct
15 Correct 1404 ms 221012 KB Output is correct
16 Correct 1438 ms 221148 KB Output is correct
17 Correct 1308 ms 197488 KB Output is correct
18 Correct 1283 ms 196368 KB Output is correct
19 Correct 1446 ms 208852 KB Output is correct
20 Correct 1286 ms 196592 KB Output is correct
21 Correct 1460 ms 202984 KB Output is correct
22 Correct 1481 ms 202940 KB Output is correct
23 Correct 1302 ms 190464 KB Output is correct
24 Correct 1211 ms 212756 KB Output is correct
25 Correct 1328 ms 178620 KB Output is correct
26 Correct 1479 ms 202816 KB Output is correct
27 Correct 1899 ms 199596 KB Output is correct
28 Correct 1938 ms 202116 KB Output is correct
29 Correct 1928 ms 215508 KB Output is correct
30 Correct 1693 ms 203192 KB Output is correct
31 Correct 2001 ms 212988 KB Output is correct
32 Correct 2263 ms 212636 KB Output is correct
33 Correct 1404 ms 220192 KB Output is correct
34 Correct 1917 ms 190172 KB Output is correct
35 Correct 1969 ms 212976 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65352 KB Output is correct
2 Correct 37 ms 65364 KB Output is correct
3 Correct 81 ms 65360 KB Output is correct
4 Correct 31 ms 65500 KB Output is correct
5 Correct 43 ms 65476 KB Output is correct
6 Correct 34 ms 65376 KB Output is correct
7 Correct 1489 ms 223344 KB Output is correct
8 Correct 1510 ms 222868 KB Output is correct
9 Correct 1417 ms 254028 KB Output is correct
10 Correct 1463 ms 221128 KB Output is correct
11 Correct 1460 ms 221012 KB Output is correct
12 Correct 35 ms 65396 KB Output is correct
13 Correct 1371 ms 221000 KB Output is correct
14 Correct 1172 ms 218772 KB Output is correct
15 Correct 1404 ms 221012 KB Output is correct
16 Correct 1438 ms 221148 KB Output is correct
17 Correct 1308 ms 197488 KB Output is correct
18 Correct 1283 ms 196368 KB Output is correct
19 Correct 1446 ms 208852 KB Output is correct
20 Correct 1286 ms 196592 KB Output is correct
21 Correct 1460 ms 202984 KB Output is correct
22 Correct 1481 ms 202940 KB Output is correct
23 Correct 1302 ms 190464 KB Output is correct
24 Correct 1211 ms 212756 KB Output is correct
25 Correct 1328 ms 178620 KB Output is correct
26 Correct 1479 ms 202816 KB Output is correct
27 Correct 1899 ms 199596 KB Output is correct
28 Correct 1938 ms 202116 KB Output is correct
29 Correct 1928 ms 215508 KB Output is correct
30 Correct 1693 ms 203192 KB Output is correct
31 Correct 2001 ms 212988 KB Output is correct
32 Correct 2263 ms 212636 KB Output is correct
33 Correct 1404 ms 220192 KB Output is correct
34 Correct 1917 ms 190172 KB Output is correct
35 Correct 1969 ms 212976 KB Output is correct
36 Correct 3333 ms 216248 KB Output is correct
37 Correct 3323 ms 265888 KB Output is correct
38 Correct 3094 ms 255192 KB Output is correct
39 Correct 3360 ms 290708 KB Output is correct
40 Correct 3356 ms 291080 KB Output is correct
41 Correct 1391 ms 291900 KB Output is correct
42 Correct 3205 ms 249504 KB Output is correct
43 Correct 3178 ms 253180 KB Output is correct