oj.uz

Submission #879390

# Submission time Handle Problem Language Result Execution time Memory
879390 2023-11-27T09:42:18 Z willychan Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1110176 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;
		}
	}
	}
	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 18 ms 88572 KB Output is correct
2 Correct 51 ms 281660 KB Output is correct
3 Correct 174 ms 281664 KB Output is correct
4 Correct 9 ms 67160 KB Output is correct
5 Correct 90 ms 281624 KB Output is correct
6 Correct 40 ms 281572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1938 ms 387180 KB Output is correct
2 Correct 1881 ms 440928 KB Output is correct
3 Correct 1813 ms 425032 KB Output is correct
4 Correct 1997 ms 448628 KB Output is correct
5 Correct 1977 ms 456304 KB Output is correct
6 Correct 11 ms 67164 KB Output is correct
7 Correct 1879 ms 429440 KB Output is correct
8 Correct 1526 ms 468544 KB Output is correct
9 Correct 1898 ms 417412 KB Output is correct
10 Correct 1992 ms 448100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 88572 KB Output is correct
2 Correct 51 ms 281660 KB Output is correct
3 Correct 174 ms 281664 KB Output is correct
4 Correct 9 ms 67160 KB Output is correct
5 Correct 90 ms 281624 KB Output is correct
6 Correct 40 ms 281572 KB Output is correct
7 Correct 1938 ms 387180 KB Output is correct
8 Correct 1881 ms 440928 KB Output is correct
9 Correct 1813 ms 425032 KB Output is correct
10 Correct 1997 ms 448628 KB Output is correct
11 Correct 1977 ms 456304 KB Output is correct
12 Correct 11 ms 67164 KB Output is correct
13 Correct 1879 ms 429440 KB Output is correct
14 Correct 1526 ms 468544 KB Output is correct
15 Correct 1898 ms 417412 KB Output is correct
16 Correct 1992 ms 448100 KB Output is correct
17 Correct 2305 ms 416488 KB Output is correct
18 Correct 2227 ms 432272 KB Output is correct
19 Correct 2194 ms 456300 KB Output is correct
20 Correct 2217 ms 436588 KB Output is correct
21 Correct 2249 ms 449756 KB Output is correct
22 Correct 2310 ms 460548 KB Output is correct
23 Correct 2248 ms 432544 KB Output is correct
24 Correct 1721 ms 475672 KB Output is correct
25 Correct 2220 ms 418684 KB Output is correct
26 Correct 2311 ms 463488 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 88572 KB Output is correct
2 Correct 51 ms 281660 KB Output is correct
3 Correct 174 ms 281664 KB Output is correct
4 Correct 9 ms 67160 KB Output is correct
5 Correct 90 ms 281624 KB Output is correct
6 Correct 40 ms 281572 KB Output is correct
7 Correct 1938 ms 387180 KB Output is correct
8 Correct 1881 ms 440928 KB Output is correct
9 Correct 1813 ms 425032 KB Output is correct
10 Correct 1997 ms 448628 KB Output is correct
11 Correct 1977 ms 456304 KB Output is correct
12 Correct 11 ms 67164 KB Output is correct
13 Correct 1879 ms 429440 KB Output is correct
14 Correct 1526 ms 468544 KB Output is correct
15 Correct 1898 ms 417412 KB Output is correct
16 Correct 1992 ms 448100 KB Output is correct
17 Correct 2305 ms 416488 KB Output is correct
18 Correct 2227 ms 432272 KB Output is correct
19 Correct 2194 ms 456300 KB Output is correct
20 Correct 2217 ms 436588 KB Output is correct
21 Correct 2249 ms 449756 KB Output is correct
22 Correct 2310 ms 460548 KB Output is correct
23 Correct 2248 ms 432544 KB Output is correct
24 Correct 1721 ms 475672 KB Output is correct
25 Correct 2220 ms 418684 KB Output is correct
26 Correct 2311 ms 463488 KB Output is correct
27 Correct 3964 ms 585184 KB Output is correct
28 Correct 3927 ms 605532 KB Output is correct
29 Correct 4019 ms 621040 KB Output is correct
30 Correct 3976 ms 612928 KB Output is correct
31 Correct 4224 ms 642156 KB Output is correct
32 Correct 4198 ms 623276 KB Output is correct
33 Correct 2449 ms 571120 KB Output is correct
34 Correct 4214 ms 579640 KB Output is correct
35 Correct 4348 ms 624828 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 88572 KB Output is correct
2 Correct 51 ms 281660 KB Output is correct
3 Correct 174 ms 281664 KB Output is correct
4 Correct 9 ms 67160 KB Output is correct
5 Correct 90 ms 281624 KB Output is correct
6 Correct 40 ms 281572 KB Output is correct
7 Correct 1938 ms 387180 KB Output is correct
8 Correct 1881 ms 440928 KB Output is correct
9 Correct 1813 ms 425032 KB Output is correct
10 Correct 1997 ms 448628 KB Output is correct
11 Correct 1977 ms 456304 KB Output is correct
12 Correct 11 ms 67164 KB Output is correct
13 Correct 1879 ms 429440 KB Output is correct
14 Correct 1526 ms 468544 KB Output is correct
15 Correct 1898 ms 417412 KB Output is correct
16 Correct 1992 ms 448100 KB Output is correct
17 Correct 2305 ms 416488 KB Output is correct
18 Correct 2227 ms 432272 KB Output is correct
19 Correct 2194 ms 456300 KB Output is correct
20 Correct 2217 ms 436588 KB Output is correct
21 Correct 2249 ms 449756 KB Output is correct
22 Correct 2310 ms 460548 KB Output is correct
23 Correct 2248 ms 432544 KB Output is correct
24 Correct 1721 ms 475672 KB Output is correct
25 Correct 2220 ms 418684 KB Output is correct
26 Correct 2311 ms 463488 KB Output is correct
27 Correct 3964 ms 585184 KB Output is correct
28 Correct 3927 ms 605532 KB Output is correct
29 Correct 4019 ms 621040 KB Output is correct
30 Correct 3976 ms 612928 KB Output is correct
31 Correct 4224 ms 642156 KB Output is correct
32 Correct 4198 ms 623276 KB Output is correct
33 Correct 2449 ms 571120 KB Output is correct
34 Correct 4214 ms 579640 KB Output is correct
35 Correct 4348 ms 624828 KB Output is correct
36 Execution timed out 9099 ms 1110176 KB Time limit exceeded
37 Halted 0 ms 0 KB -