oj.uz

Submission #748967

# Submission time Handle Problem Language Result Execution time Memory
748967 2023-05-27T08:22:18 Z model_code Cyberland (APIO23_cyberland) C++17
97 / 100
 7000 ms 234944 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define int long long
#define pb push_back

const lo inf = 1000000000000000000;
const lo li = 100005;

int n,m,k;
int arr[li],flag,t,vis[li][100],h,connected[li];
double pw[100];
vector<pair<int,int>> v[li];
vector<int> vec;

inline void dfss(int node){
	if(connected[node])return;
	//~ cout<<node<<" :: "<<endl;
	connected[node]=1;
	if(node==h)return ;
	for(auto go:v[node]){
		if(connected[go.fi]==0)dfss(go.fi);
	}
}

inline double sp(){
	priority_queue<pair<double,pair<int,int>>> pq;
	for(auto go:vec){
		for(int i=0;i<=k;i++){
			pq.push({0,{i,go}});
		}
	}
	flag=0;
	while(pq.size()){
		double tim=-pq.top().fi;
		int div=pq.top().se.fi;
		int node=pq.top().se.se;
		pq.pop();
		if(div<0)continue;
		if(vis[node][div])continue;
		vis[node][div]=1;
		if(node==h && div==0)
            return tim;
		if(node==h)continue;
		for(auto go:v[node]){
			int yes=div;
			if (vis[go.fi][yes]==0)
				pq.push({-tim-go.se/pw[div],{yes,go.fi}});
				// don't use div on the node
			if(arr[go.fi]==2){
				yes--;
				if(yes>=0 && vis[go.fi][yes]==0)
					pq.push({-tim-go.se/pw[div],{yes,go.fi}});
					// use div on the node
			}
		}
	}
    return -1;
}

double solve(int32_t N, int32_t M, int32_t K, int32_t H,
             vector<int32_t> x,vector<int32_t> y,vector<int32_t> c,vector<int32_t> _arr){
	pw[0]=1;
	for(int i=1;i<=95;i++){
		pw[i]=pw[i-1]+pw[i-1];
	}
	n=N;
    m=M;
    k=min(K,95);
    h=H;
    vec.clear();
	vec.pb(0);
	for(int i=0;i<n;i++){
		v[i].clear();
		connected[i]=0;
		for(int j=0;j<=k;j++)vis[i][j]=0;
        arr[i]=_arr[i];
	}
	for(int i=0;i<m;i++){
		v[x[i]].pb({y[i],c[i]});
		v[y[i]].pb({x[i],c[i]});
	}
	dfss(0);
    for(int i=0;i<n;i++){
		if(arr[i]==0 && connected[i])vec.pb(i);
	}
	if(connected[h]==0) return -1;
	return sp();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2756 KB Correct.
2 Correct 52 ms 2776 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3776 KB Correct.
2 Correct 215 ms 3636 KB Correct.
3 Correct 203 ms 3604 KB Correct.
4 Correct 213 ms 3688 KB Correct.
5 Correct 206 ms 3872 KB Correct.
6 Correct 211 ms 11532 KB Correct.
7 Correct 288 ms 11232 KB Correct.
8 Correct 147 ms 20052 KB Correct.
9 Correct 171 ms 2912 KB Correct.
10 Correct 164 ms 2820 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 4832 KB Correct.
2 Correct 414 ms 4992 KB Correct.
3 Correct 386 ms 5060 KB Correct.
4 Correct 298 ms 2960 KB Correct.
5 Correct 299 ms 2956 KB Correct.
6 Correct 106 ms 16092 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 66464 KB Correct.
2 Correct 283 ms 4836 KB Correct.
3 Correct 245 ms 4792 KB Correct.
4 Correct 275 ms 4924 KB Correct.
5 Correct 204 ms 2936 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 3852 KB Correct.
2 Correct 165 ms 3816 KB Correct.
3 Correct 170 ms 4008 KB Correct.
4 Correct 225 ms 12444 KB Correct.
5 Correct 113 ms 2828 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 4952 KB Correct.
2 Correct 208 ms 5072 KB Correct.
3 Correct 67 ms 69516 KB Correct.
4 Correct 227 ms 18964 KB Correct.
5 Correct 174 ms 2976 KB Correct.
6 Correct 249 ms 5032 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 5104 KB Correct.
2 Correct 66 ms 6852 KB Correct.
3 Correct 94 ms 87216 KB Correct.
4 Correct 75 ms 22548 KB Correct.
5 Correct 1984 ms 87240 KB Correct.
6 Correct 1418 ms 66152 KB Correct.
7 Correct 64 ms 24264 KB Correct.
8 Correct 64 ms 5964 KB Correct.
9 Correct 299 ms 5172 KB Correct.
10 Correct 265 ms 5044 KB Correct.
11 Correct 79 ms 3980 KB Correct.
12 Correct 336 ms 5100 KB Correct.
13 Correct 334 ms 5128 KB Correct.
14 Correct 76 ms 44060 KB Correct.
15 Correct 67 ms 14032 KB Correct.
16 Correct 309 ms 5152 KB Correct.
17 Correct 369 ms 5128 KB Correct.
18 Correct 332 ms 5204 KB Correct.
19 Correct 692 ms 5136 KB Correct.
20 Correct 20 ms 2932 KB Correct.
21 Correct 22 ms 4652 KB Correct.
22 Correct 79 ms 10300 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 8512 KB Correct.
2 Correct 204 ms 10456 KB Correct.
3 Correct 1020 ms 92524 KB Correct.
4 Correct 245 ms 9004 KB Correct.
5 Execution timed out 7104 ms 234944 KB Time limit exceeded
6 Halted 0 ms 0 KB -