oj.uz

Submission #415872

# Submission time Handle Problem Language Result Execution time Memory
415872 2021-06-01T16:11:36 Z koioi.org-koosaga Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 219872 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> qq[96][96];
vector<pi> prec[96][96];
lint ret[3000005];
lint S;
 
void Do(int u, int n){
	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++){
			for(int j = 0; j < n; j++){
				if(dist2[j] <= S && dist1[i] >= 0){
					prec[i][j].emplace_back(dist1[i], dist2[j] - dist1[i]);
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			sort(all(prec[i][j]));
			int ptr = sz(prec[i][j]);
			lint curMin = 1e18;
			for(auto &[x, y] : qq[i][j]){
				while(ptr > 0 && prec[i][j][ptr - 1].first >= x){
					curMin = min(curMin, prec[i][j][--ptr].second);
				}
				ret[y] = min(ret[y], curMin);
			}
			prec[i][j].clear();
		}
	}
}
 
// 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]]);
            }
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
        	sort(all(qq[i][j]));
        	reverse(all(qq[i][j]));
        }
    }
    for(int i = 0; i < N; i++){
    	Do(i, N);
	}
    vector<lint> ans(ret, ret + Q);
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65448 KB Output is correct
2 Correct 37 ms 65396 KB Output is correct
3 Correct 111 ms 65408 KB Output is correct
4 Correct 30 ms 65404 KB Output is correct
5 Correct 39 ms 65472 KB Output is correct
6 Correct 35 ms 65600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4549 ms 179656 KB Output is correct
2 Correct 3994 ms 195064 KB Output is correct
3 Correct 4139 ms 207748 KB Output is correct
4 Correct 4613 ms 194812 KB Output is correct
5 Correct 4940 ms 194816 KB Output is correct
6 Correct 31 ms 65356 KB Output is correct
7 Correct 4891 ms 184008 KB Output is correct
8 Correct 3638 ms 206804 KB Output is correct
9 Correct 4250 ms 172060 KB Output is correct
10 Correct 4408 ms 194424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65448 KB Output is correct
2 Correct 37 ms 65396 KB Output is correct
3 Correct 111 ms 65408 KB Output is correct
4 Correct 30 ms 65404 KB Output is correct
5 Correct 39 ms 65472 KB Output is correct
6 Correct 35 ms 65600 KB Output is correct
7 Correct 4549 ms 179656 KB Output is correct
8 Correct 3994 ms 195064 KB Output is correct
9 Correct 4139 ms 207748 KB Output is correct
10 Correct 4613 ms 194812 KB Output is correct
11 Correct 4940 ms 194816 KB Output is correct
12 Correct 31 ms 65356 KB Output is correct
13 Correct 4891 ms 184008 KB Output is correct
14 Correct 3638 ms 206804 KB Output is correct
15 Correct 4250 ms 172060 KB Output is correct
16 Correct 4408 ms 194424 KB Output is correct
17 Correct 4536 ms 190792 KB Output is correct
18 Correct 4179 ms 189692 KB Output is correct
19 Correct 3687 ms 206632 KB Output is correct
20 Correct 4074 ms 190444 KB Output is correct
21 Correct 4460 ms 200924 KB Output is correct
22 Correct 4780 ms 200508 KB Output is correct
23 Correct 4719 ms 188076 KB Output is correct
24 Correct 3805 ms 212752 KB Output is correct
25 Correct 4420 ms 176500 KB Output is correct
26 Correct 4632 ms 200956 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65448 KB Output is correct
2 Correct 37 ms 65396 KB Output is correct
3 Correct 111 ms 65408 KB Output is correct
4 Correct 30 ms 65404 KB Output is correct
5 Correct 39 ms 65472 KB Output is correct
6 Correct 35 ms 65600 KB Output is correct
7 Correct 4549 ms 179656 KB Output is correct
8 Correct 3994 ms 195064 KB Output is correct
9 Correct 4139 ms 207748 KB Output is correct
10 Correct 4613 ms 194812 KB Output is correct
11 Correct 4940 ms 194816 KB Output is correct
12 Correct 31 ms 65356 KB Output is correct
13 Correct 4891 ms 184008 KB Output is correct
14 Correct 3638 ms 206804 KB Output is correct
15 Correct 4250 ms 172060 KB Output is correct
16 Correct 4408 ms 194424 KB Output is correct
17 Correct 4536 ms 190792 KB Output is correct
18 Correct 4179 ms 189692 KB Output is correct
19 Correct 3687 ms 206632 KB Output is correct
20 Correct 4074 ms 190444 KB Output is correct
21 Correct 4460 ms 200924 KB Output is correct
22 Correct 4780 ms 200508 KB Output is correct
23 Correct 4719 ms 188076 KB Output is correct
24 Correct 3805 ms 212752 KB Output is correct
25 Correct 4420 ms 176500 KB Output is correct
26 Correct 4632 ms 200956 KB Output is correct
27 Correct 7462 ms 194488 KB Output is correct
28 Correct 7579 ms 196716 KB Output is correct
29 Correct 6554 ms 210288 KB Output is correct
30 Correct 6353 ms 197332 KB Output is correct
31 Correct 8064 ms 207448 KB Output is correct
32 Correct 7886 ms 207096 KB Output is correct
33 Correct 5300 ms 219872 KB Output is correct
34 Correct 7848 ms 184056 KB Output is correct
35 Correct 8114 ms 207352 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65448 KB Output is correct
2 Correct 37 ms 65396 KB Output is correct
3 Correct 111 ms 65408 KB Output is correct
4 Correct 30 ms 65404 KB Output is correct
5 Correct 39 ms 65472 KB Output is correct
6 Correct 35 ms 65600 KB Output is correct
7 Correct 4549 ms 179656 KB Output is correct
8 Correct 3994 ms 195064 KB Output is correct
9 Correct 4139 ms 207748 KB Output is correct
10 Correct 4613 ms 194812 KB Output is correct
11 Correct 4940 ms 194816 KB Output is correct
12 Correct 31 ms 65356 KB Output is correct
13 Correct 4891 ms 184008 KB Output is correct
14 Correct 3638 ms 206804 KB Output is correct
15 Correct 4250 ms 172060 KB Output is correct
16 Correct 4408 ms 194424 KB Output is correct
17 Correct 4536 ms 190792 KB Output is correct
18 Correct 4179 ms 189692 KB Output is correct
19 Correct 3687 ms 206632 KB Output is correct
20 Correct 4074 ms 190444 KB Output is correct
21 Correct 4460 ms 200924 KB Output is correct
22 Correct 4780 ms 200508 KB Output is correct
23 Correct 4719 ms 188076 KB Output is correct
24 Correct 3805 ms 212752 KB Output is correct
25 Correct 4420 ms 176500 KB Output is correct
26 Correct 4632 ms 200956 KB Output is correct
27 Correct 7462 ms 194488 KB Output is correct
28 Correct 7579 ms 196716 KB Output is correct
29 Correct 6554 ms 210288 KB Output is correct
30 Correct 6353 ms 197332 KB Output is correct
31 Correct 8064 ms 207448 KB Output is correct
32 Correct 7886 ms 207096 KB Output is correct
33 Correct 5300 ms 219872 KB Output is correct
34 Correct 7848 ms 184056 KB Output is correct
35 Correct 8114 ms 207352 KB Output is correct
36 Execution timed out 9102 ms 155256 KB Time limit exceeded
37 Halted 0 ms 0 KB -