Submission #1061428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061428		Gangsta	Cyberland (APIO23_cyberland)	C++17	0 / 100	381 ms	16732 KiB

cyberland

#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

vector <long double> dis(N,1e15);

priority_queue <pair<long double, int>> pq;

vector <pii> v[N];

void dij(vector<int>arr){
	pq.push({0,0});
	dis[0] = 0;
	while(!pq.empty()){
		int a = pq.top().ss;
		pq.pop();
		for(auto i: v[a]){
			if(arr[i.ff] == 0 and dis[a] < dis[i.ff]){
				dis[i.ff] = dis[a];
				pq.push({-dis[i.ff],i.ff});
			}
			else if(arr[i.ff] == 1 and dis[a] + i.ss < dis[i.ff]){
				dis[i.ff] = dis[a] + i.ss;
				pq.push({-dis[i.ff],i.ff});
			}
			else if(arr[i.ff] == 2 and dis[a] + (long double)(i.ss/2) < dis[i.ff]){
				dis[i.ff] = (long double)(i.ss/2);
				pq.push({-dis[i.ff],i.ff});
			}
		}
	}
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
	for(int i = 1; i <= m; i++){
		v[x[i]].pb({y[i],c[i]});
		v[y[i]].pb({x[i],c[i]});
	}
	dij(arr);
	return dis[h];
}

// int main(){
//     ios::sync_with_stdio(false); cin.tie(nullptr);
// }

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