Submission #926910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
926910	2024-02-14T04:15:03 Z	Wansur	Cyberland (APIO23_cyberland)	C++17	100 / 100	1183 ms	100180 KB

cyberland

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
  
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
 
using namespace std;
typedef long long ll;
const int mx=1e5+12;
 
vector<pair<int,int>> g[mx];
double d[mx][101];
bool was[mx][101];
bool used[mx];
 
struct node{
	int v,x;
	double w;
	friend bool operator <(node a,node b){
        return a.w > b.w;
    }
};
 
void dfs(int v){
	used[v]=1;
	for(auto to:g[v]){
		if(!used[to.f]){
			dfs(to.f);
		}
	}
}
 
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	k=min(k,67);
	for(int i=0;i<n;i++){
		g[i].clear();
		used[i]=0;
	}
	for(int i=0;i<m;i++){
		g[x[i]].push_back({y[i],c[i]});
		g[y[i]].push_back({x[i],c[i]});
	}
	dfs(0);
	if(!used[h]){
		return -1;
	}
	for(int i=0;i<n;i++){
		for(int x=0;x<=k+1;x++){
			d[i][x]=1e18;
			was[i][x]=0;
		}
		used[i]=0;
	}
	used[h]=1;
	dfs(0);
	priority_queue<node> s;
	d[0][0]=0;
	s.push({0,0,0});
	for(int i=0;i<n;i++){
		if(used[i] && arr[i]==0){
			d[i][0]=0;
			s.push({i,0,0});
		}
	}
	vector<pair<int,int>> q;
	for(int x=0;x<=k;x++){
		while(s.size()){
			int v=s.top().v,x=s.top().x;
			double w=s.top().w;
			s.pop();
			if(v==h)continue;
			if(w>d[v][x]){
				continue;
			}
			for(const auto &To:g[v]){
				if(d[To.f][x]>d[v][x]+To.s){
					d[To.f][x]=d[v][x]+To.s;
					s.push({To.f,x,d[To.f][x]});
				}
				if(x<k && d[To.f][x+1]>d[v][x]/2+To.s && arr[v]==2){
					d[To.f][x+1]=d[v][x]/2+To.s;
					q.push_back({To.f,x+1});
				}
			}
		}
		for(auto x:q){
			if(was[x.f][x.s])continue;
			was[x.f][x.s]=1;
			s.push({x.f,x.s,d[x.f][x.s]});
		}
	}
	double ans=1e18;
	for(int x=k;x>=0;x--){
		if(d[h][x]>=1e18)continue;
		ans=min(ans,d[h][x]);
		if(arr[h]==2 && x>0 && d[h][x-1]<2e14)ans=min(ans,d[h][x-1]/(double)2.0);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	5464 KB	Correct.
2	Correct	17 ms	5552 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	9836 KB	Correct.
2	Correct	22 ms	9820 KB	Correct.
3	Correct	21 ms	9764 KB	Correct.
4	Correct	22 ms	9820 KB	Correct.
5	Correct	22 ms	9800 KB	Correct.
6	Correct	25 ms	16440 KB	Correct.
7	Correct	26 ms	16472 KB	Correct.
8	Correct	15 ms	25500 KB	Correct.
9	Correct	20 ms	5564 KB	Correct.
10	Correct	19 ms	5468 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	9816 KB	Correct.
2	Correct	22 ms	9816 KB	Correct.
3	Correct	21 ms	10072 KB	Correct.
4	Correct	21 ms	5468 KB	Correct.
5	Correct	21 ms	5464 KB	Correct.
6	Correct	7 ms	14428 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	66060 KB	Correct.
2	Correct	119 ms	9996 KB	Correct.
3	Correct	107 ms	10440 KB	Correct.
4	Correct	110 ms	9972 KB	Correct.
5	Correct	63 ms	5464 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	9820 KB	Correct.
2	Correct	20 ms	9856 KB	Correct.
3	Correct	20 ms	9820 KB	Correct.
4	Correct	21 ms	16732 KB	Correct.
5	Correct	21 ms	5468 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	9820 KB	Correct.
2	Correct	17 ms	9884 KB	Correct.
3	Correct	31 ms	8532 KB	Correct.
4	Correct	14 ms	12380 KB	Correct.
5	Correct	18 ms	5468 KB	Correct.
6	Correct	19 ms	9820 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	10348 KB	Correct.
2	Correct	21 ms	10264 KB	Correct.
3	Correct	498 ms	96596 KB	Correct.
4	Correct	244 ms	27692 KB	Correct.
5	Correct	532 ms	52528 KB	Correct.
6	Correct	207 ms	30172 KB	Correct.
7	Correct	242 ms	29868 KB	Correct.
8	Correct	201 ms	12004 KB	Correct.
9	Correct	101 ms	10104 KB	Correct.
10	Correct	91 ms	10084 KB	Correct.
11	Correct	170 ms	9904 KB	Correct.
12	Correct	116 ms	10112 KB	Correct.
13	Correct	124 ms	10072 KB	Correct.
14	Correct	240 ms	52524 KB	Correct.
15	Correct	217 ms	18852 KB	Correct.
16	Correct	112 ms	10088 KB	Correct.
17	Correct	134 ms	10080 KB	Correct.
18	Correct	118 ms	10332 KB	Correct.
19	Correct	294 ms	10040 KB	Correct.
20	Correct	7 ms	5468 KB	Correct.
21	Correct	9 ms	5724 KB	Correct.
22	Correct	17 ms	10748 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	265 ms	10284 KB	Correct.
2	Correct	45 ms	10544 KB	Correct.
3	Correct	782 ms	100180 KB	Correct.
4	Correct	279 ms	14712 KB	Correct.
5	Correct	1183 ms	77404 KB	Correct.
6	Correct	494 ms	37388 KB	Correct.
7	Correct	418 ms	41512 KB	Correct.
8	Correct	242 ms	10060 KB	Correct.
9	Correct	207 ms	10440 KB	Correct.
10	Correct	188 ms	10320 KB	Correct.
11	Correct	248 ms	5768 KB	Correct.
12	Correct	244 ms	11376 KB	Correct.
13	Correct	254 ms	11260 KB	Correct.
14	Correct	955 ms	47720 KB	Correct.
15	Correct	813 ms	56640 KB	Correct.
16	Correct	419 ms	25448 KB	Correct.
17	Correct	268 ms	14164 KB	Correct.
18	Correct	224 ms	11220 KB	Correct.
19	Correct	278 ms	11524 KB	Correct.
20	Correct	257 ms	11348 KB	Correct.
21	Correct	658 ms	12880 KB	Correct.
22	Correct	14 ms	5500 KB	Correct.
23	Correct	18 ms	5980 KB	Correct.
24	Correct	32 ms	11512 KB	Correct.

Submission #926910

Compilation message