oj.uz

Submission #919265

# Submission time Handle Problem Language Result Execution time Memory
919265 2024-01-31T13:43:36 Z djs100201 Cyberland (APIO23_cyberland) C++17
100 / 100
 2148 ms 144464 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7512 KB Correct.
2 Correct 16 ms 7768 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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.