답안 #919265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919265	2024-01-31T13:43:36 Z	djs100201	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	2148 ms	144464 KB

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	7512 KB	Correct.
2	Correct	16 ms	7768 KB	Correct.

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	9560 KB	Correct.
2	Correct	23 ms	10576 KB	Correct.
3	Correct	24 ms	10648 KB	Correct.
4	Correct	23 ms	10776 KB	Correct.
5	Correct	23 ms	10584 KB	Correct.
6	Correct	25 ms	21592 KB	Correct.
7	Correct	28 ms	21836 KB	Correct.
8	Correct	19 ms	34392 KB	Correct.
9	Correct	22 ms	8280 KB	Correct.
10	Correct	21 ms	8280 KB	Correct.

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	9560 KB	Correct.
2	Correct	19 ms	10584 KB	Correct.
3	Correct	18 ms	10584 KB	Correct.
4	Correct	21 ms	8280 KB	Correct.
5	Correct	19 ms	8280 KB	Correct.
6	Correct	7 ms	18520 KB	Correct.

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	86608 KB	Correct.
2	Correct	20 ms	9560 KB	Correct.
3	Correct	18 ms	10584 KB	Correct.
4	Correct	20 ms	10584 KB	Correct.
5	Correct	26 ms	8280 KB	Correct.

Subtask #5
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	9816 KB	Correct.
2	Correct	24 ms	10840 KB	Correct.
3	Correct	24 ms	11100 KB	Correct.
4	Correct	28 ms	22268 KB	Correct.
5	Correct	21 ms	8280 KB	Correct.

Subtask #6
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	9848 KB	Correct.
2	Correct	19 ms	10584 KB	Correct.
3	Correct	61 ms	112532 KB	Correct.
4	Correct	18 ms	17240 KB	Correct.
5	Correct	21 ms	8280 KB	Correct.
6	Correct	20 ms	10832 KB	Correct.

Subtask #7
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	9708 KB	Correct.
2	Correct	19 ms	9992 KB	Correct.
3	Correct	922 ms	139480 KB	Correct.
4	Correct	332 ms	38588 KB	Correct.
5	Correct	386 ms	61412 KB	Correct.
6	Correct	198 ms	27600 KB	Correct.
7	Correct	357 ms	42676 KB	Correct.
8	Correct	204 ms	14008 KB	Correct.
9	Correct	79 ms	10832 KB	Correct.
10	Correct	64 ms	10832 KB	Correct.
11	Correct	147 ms	11676 KB	Correct.
12	Correct	79 ms	10832 KB	Correct.
13	Correct	80 ms	10872 KB	Correct.
14	Correct	365 ms	71136 KB	Correct.
15	Correct	316 ms	27472 KB	Correct.
16	Correct	85 ms	10744 KB	Correct.
17	Correct	82 ms	10784 KB	Correct.
18	Correct	77 ms	10832 KB	Correct.
19	Correct	91 ms	11604 KB	Correct.
20	Correct	9 ms	7512 KB	Correct.
21	Correct	8 ms	9560 KB	Correct.
22	Correct	18 ms	8536 KB	Correct.

Subtask #8
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	10084 KB	Correct.
2	Correct	41 ms	10328 KB	Correct.
3	Correct	2148 ms	144464 KB	Correct.
4	Correct	412 ms	18948 KB	Correct.
5	Correct	842 ms	69628 KB	Correct.
6	Correct	425 ms	32196 KB	Correct.
7	Correct	770 ms	58960 KB	Correct.
8	Correct	258 ms	12116 KB	Correct.
9	Correct	170 ms	10920 KB	Correct.
10	Correct	141 ms	11312 KB	Correct.
11	Correct	367 ms	8684 KB	Correct.
12	Correct	166 ms	11096 KB	Correct.
13	Correct	178 ms	11096 KB	Correct.
14	Correct	1707 ms	62992 KB	Correct.
15	Correct	1482 ms	75688 KB	Correct.
16	Correct	608 ms	34164 KB	Correct.
17	Correct	334 ms	13904 KB	Correct.
18	Correct	189 ms	11104 KB	Correct.
19	Correct	184 ms	11076 KB	Correct.
20	Correct	177 ms	11308 KB	Correct.
21	Correct	197 ms	11856 KB	Correct.
22	Correct	20 ms	7512 KB	Correct.
23	Correct	17 ms	9736 KB	Correct.
24	Correct	37 ms	8924 KB	Correct.

답안 #919265

Compilation message