oj.uz

Submission #879401

# Submission time Handle Problem Language Result Execution time Memory
879401 2023-11-27T10:09:32 Z willychan Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1154632 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization (unroll-loops)
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("O3")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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;
}

Compilation message

escape_route.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization (unroll-loops)
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 88684 KB Output is correct
2 Correct 130 ms 281828 KB Output is correct
3 Correct 245 ms 281832 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 175 ms 281572 KB Output is correct
6 Correct 40 ms 281724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2506 ms 430044 KB Output is correct
2 Correct 2541 ms 453368 KB Output is correct
3 Correct 2343 ms 434736 KB Output is correct
4 Correct 2534 ms 463096 KB Output is correct
5 Correct 2446 ms 463048 KB Output is correct
6 Correct 12 ms 67164 KB Output is correct
7 Correct 2409 ms 434044 KB Output is correct
8 Correct 2035 ms 475444 KB Output is correct
9 Correct 2331 ms 422256 KB Output is correct
10 Correct 2517 ms 462592 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 88684 KB Output is correct
2 Correct 130 ms 281828 KB Output is correct
3 Correct 245 ms 281832 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 175 ms 281572 KB Output is correct
6 Correct 40 ms 281724 KB Output is correct
7 Correct 2506 ms 430044 KB Output is correct
8 Correct 2541 ms 453368 KB Output is correct
9 Correct 2343 ms 434736 KB Output is correct
10 Correct 2534 ms 463096 KB Output is correct
11 Correct 2446 ms 463048 KB Output is correct
12 Correct 12 ms 67164 KB Output is correct
13 Correct 2409 ms 434044 KB Output is correct
14 Correct 2035 ms 475444 KB Output is correct
15 Correct 2331 ms 422256 KB Output is correct
16 Correct 2517 ms 462592 KB Output is correct
17 Correct 2644 ms 432972 KB Output is correct
18 Correct 2598 ms 431960 KB Output is correct
19 Correct 2656 ms 456228 KB Output is correct
20 Correct 2585 ms 436504 KB Output is correct
21 Correct 2795 ms 465508 KB Output is correct
22 Correct 2817 ms 465232 KB Output is correct
23 Correct 2730 ms 435868 KB Output is correct
24 Correct 2203 ms 477700 KB Output is correct
25 Correct 2597 ms 423588 KB Output is correct
26 Correct 2637 ms 465312 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 88684 KB Output is correct
2 Correct 130 ms 281828 KB Output is correct
3 Correct 245 ms 281832 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 175 ms 281572 KB Output is correct
6 Correct 40 ms 281724 KB Output is correct
7 Correct 2506 ms 430044 KB Output is correct
8 Correct 2541 ms 453368 KB Output is correct
9 Correct 2343 ms 434736 KB Output is correct
10 Correct 2534 ms 463096 KB Output is correct
11 Correct 2446 ms 463048 KB Output is correct
12 Correct 12 ms 67164 KB Output is correct
13 Correct 2409 ms 434044 KB Output is correct
14 Correct 2035 ms 475444 KB Output is correct
15 Correct 2331 ms 422256 KB Output is correct
16 Correct 2517 ms 462592 KB Output is correct
17 Correct 2644 ms 432972 KB Output is correct
18 Correct 2598 ms 431960 KB Output is correct
19 Correct 2656 ms 456228 KB Output is correct
20 Correct 2585 ms 436504 KB Output is correct
21 Correct 2795 ms 465508 KB Output is correct
22 Correct 2817 ms 465232 KB Output is correct
23 Correct 2730 ms 435868 KB Output is correct
24 Correct 2203 ms 477700 KB Output is correct
25 Correct 2597 ms 423588 KB Output is correct
26 Correct 2637 ms 465312 KB Output is correct
27 Correct 4503 ms 659272 KB Output is correct
28 Correct 4391 ms 700360 KB Output is correct
29 Correct 4301 ms 722948 KB Output is correct
30 Correct 4425 ms 686468 KB Output is correct
31 Correct 4740 ms 671232 KB Output is correct
32 Correct 4922 ms 642020 KB Output is correct
33 Correct 2678 ms 647468 KB Output is correct
34 Correct 4482 ms 666432 KB Output is correct
35 Correct 4513 ms 704196 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 88684 KB Output is correct
2 Correct 130 ms 281828 KB Output is correct
3 Correct 245 ms 281832 KB Output is correct
4 Correct 9 ms 67164 KB Output is correct
5 Correct 175 ms 281572 KB Output is correct
6 Correct 40 ms 281724 KB Output is correct
7 Correct 2506 ms 430044 KB Output is correct
8 Correct 2541 ms 453368 KB Output is correct
9 Correct 2343 ms 434736 KB Output is correct
10 Correct 2534 ms 463096 KB Output is correct
11 Correct 2446 ms 463048 KB Output is correct
12 Correct 12 ms 67164 KB Output is correct
13 Correct 2409 ms 434044 KB Output is correct
14 Correct 2035 ms 475444 KB Output is correct
15 Correct 2331 ms 422256 KB Output is correct
16 Correct 2517 ms 462592 KB Output is correct
17 Correct 2644 ms 432972 KB Output is correct
18 Correct 2598 ms 431960 KB Output is correct
19 Correct 2656 ms 456228 KB Output is correct
20 Correct 2585 ms 436504 KB Output is correct
21 Correct 2795 ms 465508 KB Output is correct
22 Correct 2817 ms 465232 KB Output is correct
23 Correct 2730 ms 435868 KB Output is correct
24 Correct 2203 ms 477700 KB Output is correct
25 Correct 2597 ms 423588 KB Output is correct
26 Correct 2637 ms 465312 KB Output is correct
27 Correct 4503 ms 659272 KB Output is correct
28 Correct 4391 ms 700360 KB Output is correct
29 Correct 4301 ms 722948 KB Output is correct
30 Correct 4425 ms 686468 KB Output is correct
31 Correct 4740 ms 671232 KB Output is correct
32 Correct 4922 ms 642020 KB Output is correct
33 Correct 2678 ms 647468 KB Output is correct
34 Correct 4482 ms 666432 KB Output is correct
35 Correct 4513 ms 704196 KB Output is correct
36 Execution timed out 9072 ms 1154632 KB Time limit exceeded
37 Halted 0 ms 0 KB -