oj.uz

Submission #879392

# Submission time Handle Problem Language Result Execution time Memory
879392 2023-11-27T09:48:20 Z willychan Escape Route (JOI21_escape_route) C++17
70 / 100
 5587 ms 1602008 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 5e16
const int Ba = 90;
pair<ll,ll> dis[Ba][Ba][Ba*Ba];
vector<pair<int,int> > side[Ba];
bitset<Ba> reach[Ba];
pair<ll,ll> Tdis[Ba][Ba];
int cnt[Ba][Ba];
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) {
	for(int i=0;i<N;i++) side[i].clear();
    for(int i=0; i<M; i++) {
        side[A[i]].push_back({B[i],i});
        side[B[i]].push_back({A[i],i});
    }
    for(int e=0; e<M; e++) {
        int x = A[e];
        int y = B[e];
        ll disx[Ba];
        ll disy[Ba];
		for(int i=0;i<N;i++) disx[i]=disy[i]=inf;
        disx[x]=0;
        disy[y]=0;
        bitset<Ba> reachx;
        bitset<Ba> reachy;
        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]) {
                if(C[g.second]+cur.first<T)	 continue;
                if(disx[g.first]>cur.first+L[g.second]) disx[g.first]=cur.first+L[g.second];
            }
            reachx[cur.second]=1;
        }
        while(true) {
            pair<ll,int> cur = {inf,-1};
            for(int i=0; i<N; i++) if(!reachy[i]) cur = min(cur, {disy[i],i});
            if(cur.first>=inf) break;
            for(auto g : side[cur.second]) {
                if(C[g.second]-cur.first-L[g.second]-L[e]<T) continue;
                if(disy[g.first]>cur.first+L[g.second]) disy[g.first] = cur.first+L[g.second];
            }
            reachy[cur.second]=1;
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                dis[i][j][2*e] = {T-disx[i],disx[i]+disy[j]+L[e]};
            }
        }
		reachx.reset();
		reachy.reset();
		for(int i=0;i<N;i++) disx[i]=disy[i]=inf;
		disx[x]=0;
		disy[y]=0;
        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]) {
                if(C[g.second]-cur.first-L[g.second]-L[e]<T)	 continue;
                if(disx[g.first]>cur.first+L[g.second]) disx[g.first]=cur.first+L[g.second];
            }
            reachx[cur.second]=1;
        }
        while(true) {
            pair<ll,int> cur = {inf,-1};
            for(int i=0; i<N; i++) if(!reachy[i]) cur = min(cur, {disy[i],i});
            if(cur.first>=inf) break;
            for(auto g : side[cur.second]) {
                if(C[g.second]+cur.first<T) continue;
                if(disy[g.first]>cur.first+L[g.second]) disy[g.first] = cur.first+L[g.second];
            }
            reachy[cur.second]=1;
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                dis[i][j][2*e+1] = {T-disy[i],disx[j]+disy[i]+L[e]};
            }
        }
    }
	/*	
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cout<<i<<" "<<j<<":";
			for(int e=0;e<2*M;e++) cout<<"("<<dis[i][j][e].first<<" "<<dis[i][j][e].second<<") ";
			cout<<"\n";
		}
	}*/
	
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
			cnt[i][j] = 2*M-1;
            sort(dis[i][j],dis[i][j]+2*M);
            for(int e=2*M-2; e>=0; e--) dis[i][j][e].second = min(dis[i][j][e].second,dis[i][j][e+1].second);
        }
    }
	vector<vector<ll> >  dis0(N,vector<ll>(N,0));
    for(int s=0; s<N; s++) {
		reach[s].reset();
        for(int i=0; i<N; i++) dis0[s][i]=inf;
        dis0[s][s]=0;
        while(true) {
            pair<ll,int> cur = {inf,-1};
            for(int i=0; i<N; i++) if(!reach[s][i]) cur = min(cur, {dis0[s][i],i});
            if(cur.first>=inf)	break; 
            for(auto e : side[cur.second]) {
                int mind = e.second;
                if(C[mind]-L[mind]<cur.first) continue;
                if(dis0[s][e.first]>cur.first+L[mind]) {
                    dis0[s][e.first] = cur.first+L[mind];
                }
            }
            reach[s][cur.second]=1;
        }
    }
	{
	bitset<Ba> r;
	for(int s=0;s<N;s++){
		r.reset();
		for(int i=0;i<N;i++) Tdis[s][i] = {100,inf};
		Tdis[s][s]={0,0};
		while(true)	{
			pair<pair<ll,ll>,int>  cur = {{100,inf},-1};
			for(int i=0;i<N;i++){
				if(!r[i]){
					cur = min(cur,{Tdis[s][i],i});
				}
			}
			if(cur.first.first>=100 || cur.first.second>=inf) break;
			for(int i=0;i<N;i++){
				if(dis0[cur.second][i]<S){
					if(Tdis[s][i]>make_pair(cur.first.first+1,dis0[cur.second][i])){
						Tdis[s][i] = make_pair(cur.first.first+1,dis0[cur.second][i]); 
					}
				}
			}
			r[cur.second]=1;
		}
	}
	}


	if(N>60) assert(1==0);
	vector<ll> ans(Q,inf);
	vector<int> ord(Q);
	for(int i=0;i<Q;i++) ord[i]=i;
	sort(ord.begin(),ord.end(),[&](const int &a,const int &b){return T[a]>T[b];});
	/*
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cout<<i<<" "<<j<<":"<<"("<<Tdis[i][j].first<<","<<Tdis[i][j].second<<")\n";
		}
	}*/
	
	for(int k=0;k<Q;k++){
		int i = ord[k];
		int u = U[i];
		ans[i] = min(ans[i],S-T[i]+((Tdis[u][V[i]].first-1)*S)+Tdis[u][V[i]].second);
		for(int v=0;v<N;v++){
			if(v==u) continue;
			while(cnt[u][v]>=0 && dis[u][v][cnt[u][v]].first>=T[i]) cnt[u][v]--;
			if(cnt[u][v]+1>=2*M) continue;
			if(dis[u][v][cnt[u][v]+1].second+T[i]<S && dis[u][v][cnt[u][v]+1].second>0){
//				cout<<i<<":"<<v<<"\n";
				if(v==V[i]){
					ans[i] = min(ans[i],dis[u][v][cnt[u][v]+1].second);	
				}else{
					ans[i] = min(ans[i],S-T[i]+((Tdis[v][V[i]].first-1)*S)+Tdis[v][V[i]].second);
				}
			}
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 88572 KB Output is correct
2 Correct 57 ms 281588 KB Output is correct
3 Correct 169 ms 281764 KB Output is correct
4 Correct 9 ms 67168 KB Output is correct
5 Correct 91 ms 281612 KB Output is correct
6 Correct 38 ms 281468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1898 ms 387304 KB Output is correct
2 Correct 1924 ms 453364 KB Output is correct
3 Correct 1796 ms 434676 KB Output is correct
4 Correct 1894 ms 463396 KB Output is correct
5 Correct 1933 ms 463148 KB Output is correct
6 Correct 11 ms 67160 KB Output is correct
7 Correct 1835 ms 434000 KB Output is correct
8 Correct 1476 ms 475444 KB Output is correct
9 Correct 1776 ms 422440 KB Output is correct
10 Correct 1976 ms 462844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 88572 KB Output is correct
2 Correct 57 ms 281588 KB Output is correct
3 Correct 169 ms 281764 KB Output is correct
4 Correct 9 ms 67168 KB Output is correct
5 Correct 91 ms 281612 KB Output is correct
6 Correct 38 ms 281468 KB Output is correct
7 Correct 1898 ms 387304 KB Output is correct
8 Correct 1924 ms 453364 KB Output is correct
9 Correct 1796 ms 434676 KB Output is correct
10 Correct 1894 ms 463396 KB Output is correct
11 Correct 1933 ms 463148 KB Output is correct
12 Correct 11 ms 67160 KB Output is correct
13 Correct 1835 ms 434000 KB Output is correct
14 Correct 1476 ms 475444 KB Output is correct
15 Correct 1776 ms 422440 KB Output is correct
16 Correct 1976 ms 462844 KB Output is correct
17 Correct 2196 ms 433200 KB Output is correct
18 Correct 2207 ms 432424 KB Output is correct
19 Correct 2277 ms 456188 KB Output is correct
20 Correct 2128 ms 436464 KB Output is correct
21 Correct 2250 ms 465516 KB Output is correct
22 Correct 2254 ms 465236 KB Output is correct
23 Correct 2166 ms 435876 KB Output is correct
24 Correct 1683 ms 477480 KB Output is correct
25 Correct 2174 ms 423580 KB Output is correct
26 Correct 2221 ms 464976 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 88572 KB Output is correct
2 Correct 57 ms 281588 KB Output is correct
3 Correct 169 ms 281764 KB Output is correct
4 Correct 9 ms 67168 KB Output is correct
5 Correct 91 ms 281612 KB Output is correct
6 Correct 38 ms 281468 KB Output is correct
7 Correct 1898 ms 387304 KB Output is correct
8 Correct 1924 ms 453364 KB Output is correct
9 Correct 1796 ms 434676 KB Output is correct
10 Correct 1894 ms 463396 KB Output is correct
11 Correct 1933 ms 463148 KB Output is correct
12 Correct 11 ms 67160 KB Output is correct
13 Correct 1835 ms 434000 KB Output is correct
14 Correct 1476 ms 475444 KB Output is correct
15 Correct 1776 ms 422440 KB Output is correct
16 Correct 1976 ms 462844 KB Output is correct
17 Correct 2196 ms 433200 KB Output is correct
18 Correct 2207 ms 432424 KB Output is correct
19 Correct 2277 ms 456188 KB Output is correct
20 Correct 2128 ms 436464 KB Output is correct
21 Correct 2250 ms 465516 KB Output is correct
22 Correct 2254 ms 465236 KB Output is correct
23 Correct 2166 ms 435876 KB Output is correct
24 Correct 1683 ms 477480 KB Output is correct
25 Correct 2174 ms 423580 KB Output is correct
26 Correct 2221 ms 464976 KB Output is correct
27 Correct 4008 ms 591640 KB Output is correct
28 Correct 3913 ms 590848 KB Output is correct
29 Correct 3825 ms 614496 KB Output is correct
30 Correct 3819 ms 635136 KB Output is correct
31 Correct 3997 ms 665056 KB Output is correct
32 Correct 4309 ms 628528 KB Output is correct
33 Correct 2506 ms 637792 KB Output is correct
34 Correct 3969 ms 628640 KB Output is correct
35 Correct 4043 ms 673868 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 88572 KB Output is correct
2 Correct 57 ms 281588 KB Output is correct
3 Correct 169 ms 281764 KB Output is correct
4 Correct 9 ms 67168 KB Output is correct
5 Correct 91 ms 281612 KB Output is correct
6 Correct 38 ms 281468 KB Output is correct
7 Correct 1898 ms 387304 KB Output is correct
8 Correct 1924 ms 453364 KB Output is correct
9 Correct 1796 ms 434676 KB Output is correct
10 Correct 1894 ms 463396 KB Output is correct
11 Correct 1933 ms 463148 KB Output is correct
12 Correct 11 ms 67160 KB Output is correct
13 Correct 1835 ms 434000 KB Output is correct
14 Correct 1476 ms 475444 KB Output is correct
15 Correct 1776 ms 422440 KB Output is correct
16 Correct 1976 ms 462844 KB Output is correct
17 Correct 2196 ms 433200 KB Output is correct
18 Correct 2207 ms 432424 KB Output is correct
19 Correct 2277 ms 456188 KB Output is correct
20 Correct 2128 ms 436464 KB Output is correct
21 Correct 2250 ms 465516 KB Output is correct
22 Correct 2254 ms 465236 KB Output is correct
23 Correct 2166 ms 435876 KB Output is correct
24 Correct 1683 ms 477480 KB Output is correct
25 Correct 2174 ms 423580 KB Output is correct
26 Correct 2221 ms 464976 KB Output is correct
27 Correct 4008 ms 591640 KB Output is correct
28 Correct 3913 ms 590848 KB Output is correct
29 Correct 3825 ms 614496 KB Output is correct
30 Correct 3819 ms 635136 KB Output is correct
31 Correct 3997 ms 665056 KB Output is correct
32 Correct 4309 ms 628528 KB Output is correct
33 Correct 2506 ms 637792 KB Output is correct
34 Correct 3969 ms 628640 KB Output is correct
35 Correct 4043 ms 673868 KB Output is correct
36 Runtime error 5587 ms 1602008 KB Execution killed with signal 6
37 Halted 0 ms 0 KB -