oj.uz

Submission #879352

# Submission time Handle Problem Language Result Execution time Memory
879352 2023-11-27T07:42:58 Z willychan Escape Route (JOI21_escape_route) C++17
25 / 100
 9000 ms 432572 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];
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++) {
            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);
	
	
	/*
	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 i=0;i<Q;i++){
		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;
			ll  l =-1;
			ll r = 2*M;
			while(r-l>1){
				ll mid = (r+l)/2;
				if(dis[u][v][mid].first>=T[i]) r = mid;
				else l = mid;
			}
			if(r>=2*M) continue;
			if(dis[u][v][r].second+T[i]<S && dis[u][v][r].second>0){
//				cout<<i<<":"<<v<<"\n";
				if(v==V[i]){
					ans[i] = min(ans[i],dis[u][v][r].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 19 ms 88568 KB Output is correct
2 Correct 93 ms 281876 KB Output is correct
3 Correct 178 ms 281584 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 93 ms 281708 KB Output is correct
6 Correct 40 ms 281528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7300 ms 383708 KB Output is correct
2 Correct 6669 ms 394208 KB Output is correct
3 Correct 7273 ms 389604 KB Output is correct
4 Correct 7413 ms 400660 KB Output is correct
5 Correct 7364 ms 402540 KB Output is correct
6 Correct 11 ms 65144 KB Output is correct
7 Correct 7115 ms 391024 KB Output is correct
8 Correct 2473 ms 415008 KB Output is correct
9 Correct 7027 ms 379504 KB Output is correct
10 Correct 7444 ms 432572 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 88568 KB Output is correct
2 Correct 93 ms 281876 KB Output is correct
3 Correct 178 ms 281584 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 93 ms 281708 KB Output is correct
6 Correct 40 ms 281528 KB Output is correct
7 Correct 7300 ms 383708 KB Output is correct
8 Correct 6669 ms 394208 KB Output is correct
9 Correct 7273 ms 389604 KB Output is correct
10 Correct 7413 ms 400660 KB Output is correct
11 Correct 7364 ms 402540 KB Output is correct
12 Correct 11 ms 65144 KB Output is correct
13 Correct 7115 ms 391024 KB Output is correct
14 Correct 2473 ms 415008 KB Output is correct
15 Correct 7027 ms 379504 KB Output is correct
16 Correct 7444 ms 432572 KB Output is correct
17 Execution timed out 9017 ms 374760 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 88568 KB Output is correct
2 Correct 93 ms 281876 KB Output is correct
3 Correct 178 ms 281584 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 93 ms 281708 KB Output is correct
6 Correct 40 ms 281528 KB Output is correct
7 Correct 7300 ms 383708 KB Output is correct
8 Correct 6669 ms 394208 KB Output is correct
9 Correct 7273 ms 389604 KB Output is correct
10 Correct 7413 ms 400660 KB Output is correct
11 Correct 7364 ms 402540 KB Output is correct
12 Correct 11 ms 65144 KB Output is correct
13 Correct 7115 ms 391024 KB Output is correct
14 Correct 2473 ms 415008 KB Output is correct
15 Correct 7027 ms 379504 KB Output is correct
16 Correct 7444 ms 432572 KB Output is correct
17 Execution timed out 9017 ms 374760 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 88568 KB Output is correct
2 Correct 93 ms 281876 KB Output is correct
3 Correct 178 ms 281584 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 93 ms 281708 KB Output is correct
6 Correct 40 ms 281528 KB Output is correct
7 Correct 7300 ms 383708 KB Output is correct
8 Correct 6669 ms 394208 KB Output is correct
9 Correct 7273 ms 389604 KB Output is correct
10 Correct 7413 ms 400660 KB Output is correct
11 Correct 7364 ms 402540 KB Output is correct
12 Correct 11 ms 65144 KB Output is correct
13 Correct 7115 ms 391024 KB Output is correct
14 Correct 2473 ms 415008 KB Output is correct
15 Correct 7027 ms 379504 KB Output is correct
16 Correct 7444 ms 432572 KB Output is correct
17 Execution timed out 9017 ms 374760 KB Time limit exceeded
18 Halted 0 ms 0 KB -