Submission #919265

#	Time	Username	Problem	Language	Result	Execution time	Memory
919265		djs100201	Cyberland (APIO23_cyberland)	C++17	100 / 100	2148 ms	144464 KiB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =1e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
vector<P>v[n_];
long double dist[n_][81],pw[n_];
ll par[n_],par2[n_];
ll find(ll x){
	if(par[x]<0)return x;
	return par[x]=find(par[x]);
}
void merge(ll x,ll y){
	x=find(x),y=find(y);
	if(x==y)return; 
	par[x]=y;
}
ll find2(ll x){
	if(par2[x]<0)return x;
	return par2[x]=find2(par2[x]);
}
void merge2(ll x,ll y){
	x=find2(x),y=find2(y);
	if(x==y)return; 
	par2[x]=y;
}
double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> C, vector<int> arr) {
	n=N,m=M,k=min(80,K);
	for(int i=0;i<N;i++){
		par[i]=-1,par2[i]=-1;
		for(int j=0;j<=k;j++)dist[i][j]=inf;
	}
	pw[0]=1;
	for(int i=1;i<=k;i++)pw[i]=pw[i-1]*0.5;
    //return -1;
	for(int i=0;i<M;i++){
		merge(U[i],V[i]);
		v[U[i]].push_back({V[i],C[i]});
		v[V[i]].push_back({U[i],C[i]});
        if(U[i]!=H && V[i]!=H)merge2(U[i],V[i]);
	}
	if(find(0)!=find(H)){
        for(int i=0;i<N;i++)v[i].clear();
        return -1;
    }
	priority_queue<pair<long double,P>,vector<pair<long double,P>>,greater<>>pq;
	pq.push({0.0,{H,0}});
	dist[H][0]=0.0;
	double ans=inf;
	while(pq.size()){
		double a=pq.top().first;
		b=pq.top().second.first,c=pq.top().second.second;
		pq.pop();
		//cout<<a<<' '<<b<<' '<<c<<endl;
		if(dist[b][c]<a)continue;
		if(b==0){
			ans=min(ans,a);
			continue;
		}
		for(auto nxt:v[b]){
            if(find2(nxt.first)!=find2(0))continue;
			double cost=a+nxt.second*pw[c];
			if(arr[nxt.first]==0){
				if(find(nxt.first)==find(0))ans=min(ans,cost);
			}
			else if(arr[nxt.first]==1 || c==k){
				if(cost<dist[nxt.first][c]){
					dist[nxt.first][c]=cost;
					pq.push({cost,{nxt.first,c}});
				}
			}
			else{
              if(cost<dist[nxt.first][c]){
					dist[nxt.first][c]=cost;
					pq.push({cost,{nxt.first,c}});
				}
				if(cost<dist[nxt.first][c+1]){
					dist[nxt.first][c+1]=cost;
					pq.push({cost,{nxt.first,c+1}});
				}
			}
		}
	}
    for(int i=0;i<N;i++)v[i].clear();
	return ans;
}
//int main(){
  //  cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
//}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3