oj.uz

Submission #879412

# Submission time Handle Problem Language Result Execution time Memory
879412 2023-11-27T10:29:03 Z willychan Escape Route (JOI21_escape_route) C++17
70 / 100
 5815 ms 1602296 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];
ll dis0[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;
            stable_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);
        }
    }
    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 21 ms 88568 KB Output is correct
2 Correct 100 ms 281604 KB Output is correct
3 Correct 181 ms 283624 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 89 ms 283624 KB Output is correct
6 Correct 41 ms 281584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1886 ms 389256 KB Output is correct
2 Correct 1935 ms 455416 KB Output is correct
3 Correct 1807 ms 436732 KB Output is correct
4 Correct 1956 ms 464956 KB Output is correct
5 Correct 1902 ms 465296 KB Output is correct
6 Correct 10 ms 67164 KB Output is correct
7 Correct 1817 ms 436344 KB Output is correct
8 Correct 1492 ms 475568 KB Output is correct
9 Correct 1811 ms 424320 KB Output is correct
10 Correct 1951 ms 464676 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 88568 KB Output is correct
2 Correct 100 ms 281604 KB Output is correct
3 Correct 181 ms 283624 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 89 ms 283624 KB Output is correct
6 Correct 41 ms 281584 KB Output is correct
7 Correct 1886 ms 389256 KB Output is correct
8 Correct 1935 ms 455416 KB Output is correct
9 Correct 1807 ms 436732 KB Output is correct
10 Correct 1956 ms 464956 KB Output is correct
11 Correct 1902 ms 465296 KB Output is correct
12 Correct 10 ms 67164 KB Output is correct
13 Correct 1817 ms 436344 KB Output is correct
14 Correct 1492 ms 475568 KB Output is correct
15 Correct 1811 ms 424320 KB Output is correct
16 Correct 1951 ms 464676 KB Output is correct
17 Correct 2180 ms 435092 KB Output is correct
18 Correct 2170 ms 434156 KB Output is correct
19 Correct 2229 ms 457996 KB Output is correct
20 Correct 2264 ms 438524 KB Output is correct
21 Correct 2368 ms 467568 KB Output is correct
22 Correct 2447 ms 467040 KB Output is correct
23 Correct 2285 ms 437944 KB Output is correct
24 Correct 1785 ms 477708 KB Output is correct
25 Correct 2315 ms 425664 KB Output is correct
26 Correct 2403 ms 467472 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 88568 KB Output is correct
2 Correct 100 ms 281604 KB Output is correct
3 Correct 181 ms 283624 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 89 ms 283624 KB Output is correct
6 Correct 41 ms 281584 KB Output is correct
7 Correct 1886 ms 389256 KB Output is correct
8 Correct 1935 ms 455416 KB Output is correct
9 Correct 1807 ms 436732 KB Output is correct
10 Correct 1956 ms 464956 KB Output is correct
11 Correct 1902 ms 465296 KB Output is correct
12 Correct 10 ms 67164 KB Output is correct
13 Correct 1817 ms 436344 KB Output is correct
14 Correct 1492 ms 475568 KB Output is correct
15 Correct 1811 ms 424320 KB Output is correct
16 Correct 1951 ms 464676 KB Output is correct
17 Correct 2180 ms 435092 KB Output is correct
18 Correct 2170 ms 434156 KB Output is correct
19 Correct 2229 ms 457996 KB Output is correct
20 Correct 2264 ms 438524 KB Output is correct
21 Correct 2368 ms 467568 KB Output is correct
22 Correct 2447 ms 467040 KB Output is correct
23 Correct 2285 ms 437944 KB Output is correct
24 Correct 1785 ms 477708 KB Output is correct
25 Correct 2315 ms 425664 KB Output is correct
26 Correct 2403 ms 467472 KB Output is correct
27 Correct 4182 ms 613712 KB Output is correct
28 Correct 4298 ms 578008 KB Output is correct
29 Correct 4136 ms 603260 KB Output is correct
30 Correct 4215 ms 619620 KB Output is correct
31 Correct 4345 ms 655812 KB Output is correct
32 Correct 4406 ms 664812 KB Output is correct
33 Correct 2453 ms 649428 KB Output is correct
34 Correct 4080 ms 610316 KB Output is correct
35 Correct 4026 ms 686816 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 88568 KB Output is correct
2 Correct 100 ms 281604 KB Output is correct
3 Correct 181 ms 283624 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 89 ms 283624 KB Output is correct
6 Correct 41 ms 281584 KB Output is correct
7 Correct 1886 ms 389256 KB Output is correct
8 Correct 1935 ms 455416 KB Output is correct
9 Correct 1807 ms 436732 KB Output is correct
10 Correct 1956 ms 464956 KB Output is correct
11 Correct 1902 ms 465296 KB Output is correct
12 Correct 10 ms 67164 KB Output is correct
13 Correct 1817 ms 436344 KB Output is correct
14 Correct 1492 ms 475568 KB Output is correct
15 Correct 1811 ms 424320 KB Output is correct
16 Correct 1951 ms 464676 KB Output is correct
17 Correct 2180 ms 435092 KB Output is correct
18 Correct 2170 ms 434156 KB Output is correct
19 Correct 2229 ms 457996 KB Output is correct
20 Correct 2264 ms 438524 KB Output is correct
21 Correct 2368 ms 467568 KB Output is correct
22 Correct 2447 ms 467040 KB Output is correct
23 Correct 2285 ms 437944 KB Output is correct
24 Correct 1785 ms 477708 KB Output is correct
25 Correct 2315 ms 425664 KB Output is correct
26 Correct 2403 ms 467472 KB Output is correct
27 Correct 4182 ms 613712 KB Output is correct
28 Correct 4298 ms 578008 KB Output is correct
29 Correct 4136 ms 603260 KB Output is correct
30 Correct 4215 ms 619620 KB Output is correct
31 Correct 4345 ms 655812 KB Output is correct
32 Correct 4406 ms 664812 KB Output is correct
33 Correct 2453 ms 649428 KB Output is correct
34 Correct 4080 ms 610316 KB Output is correct
35 Correct 4026 ms 686816 KB Output is correct
36 Runtime error 5815 ms 1602296 KB Execution killed with signal 6
37 Halted 0 ms 0 KB -