Submission #758699

#	Time	Username	Problem	Language	Result	Execution time	Memory
758699		OrazB	Cyberland (APIO23_cyberland)	C++17	49 / 100	626 ms	2097152 KiB

cyberland

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 300005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

vector<pii> E[N];

void dfs(int nd, int h, vector<int> arr, set<pii> &q, vector<double> &dis, vector<bool> &vis){
	if (!arr[nd]){
		q.insert({0, nd});
		dis[nd] = 0;
	} 
	vis[nd] = 1;
	for (auto i : E[nd]){
		if (vis[i.ff] or i.ff == h) continue;
		dfs(i.ff, h, arr, q, dis, vis);	
	}
}

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 = 0; i < n; i++) E[i].clear();
	for (int i = 0; i < m; i++){
		E[x[i]].pb({y[i], c[i]});
		E[y[i]].pb({x[i], c[i]});	
	}
	vector<bool> vis(n+10, 0);
	vector<double> dis(n+10, 1e18);
	vector<int> cur(n+10, 0);
	set<pii> q;
	q.insert({0, 0});
	dis[0] = 0;
	dfs(0, h, arr, q, dis, vis);
	while(!q.empty()){
		int x = (*q.begin()).ss;
		q.erase(q.begin());
		if (x == h) continue;
		for (auto i : E[x]){
			int t=0;
			double res = dis[x]+i.ss;
			if (arr[i.ff] == 2){
				if (cur[x] < k){res /= 2;t=1;}
			}
			if (dis[i.ff] > res){
				q.erase({dis[i.ff], i.ff});
				dis[i.ff] = res;
				cur[i.ff] = cur[x]+t;
				q.insert({dis[i.ff], i.ff});
			}
		}
	}
	if (dis[h] == 1e18) return double(-1);
	return dis[h];
}

// int main ()
// {
// 	int n, m, k, h;
// 	cin >> n >> m >> k >> h;
// 	vector<int> x(m), y(m), c(m), arr(n);
// 	for (int i = 0; i < m; i++){
// 		cin >> x[i] >> y[i] >> c[i];
// 	}
// 	for (int i = 0; i < n; i++) cin >> arr[i];
// 	cout << solve(n,m,k,h,x,y,c,arr);
// }	

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