Submission #924885

#	Time	Username	Problem	Language	Result	Execution time	Memory
924885		pan	Cyberland (APIO23_cyberland)	C++17	15 / 100	777 ms	62220 KiB

cyberland

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ll, ld> pd;
typedef pair<string, ll> psi;
typedef pair<ll, ll> pi;
typedef pair<ld, pi> pdi;
ll const INF = LLONG_MAX;
vector<pd> adj[100005];
bool reachable[100005];
struct compare
{
	bool operator() (pdi const&  a, pdi const&  b)
	{
		return a.f>b.f; // least element come out first
	}
};
void dfs(ll from)
{
	if (reachable[from]) return;
	reachable[from] = true;
	for (pd u: adj[from]) dfs(u.f);
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr)
{
	ll n = N;
	for (ll i=0; i<N; ++i) {adj[i].clear(); adj[i].resize(0); reachable[i] = false;}
	vector<vector<ld> > dist(n+5, vector<ld> (min(75, K+1), INF));
	vector<vector<bool> > visited(n+5, vector<bool> (min(75, K+1), false));
	for (ll i=0; i<M; ++i)
	{
		adj[x[i]].pb(mp(y[i], (ld) c[i]));
		adj[y[i]].pb(mp(x[i], (ld) c[i]));
	}
	dfs(0);
	if (!reachable[H]) return -1;
	priority_queue<pdi, vector<pdi>, compare> pq;
	for (ll i=0; i<n; ++i) {if (i==0 || (reachable[i] && arr[i]==0)) {dist[i][0] = 0; pq.push(mp(0, mp(i,0)));}}
	while (pq.size())
	{
		ll city = pq.top().s.f, counter = pq.top().s.s;
		pq.pop();
		if (visited[city][counter]) continue;
		visited[city][counter] = true;
		if (city==H) continue;
		for (pd u: adj[city])
		{
			if ((ld) dist[city][counter]+u.s<dist[u.f][counter]) 
			{
				dist[u.f][counter] = dist[city][counter]+u.s;
				pq.push(mp(dist[u.f][counter], mp(u.f, counter)));
			}
			if (arr[city]==2 && counter+1<min(75, K+1) && (ld) dist[city][counter]/2+u.s<dist[u.f][counter+1])
			{
				dist[u.f][counter+1]  = (ld) dist[city][counter]/2+u.s;
				pq.push(mp(dist[u.f][counter+1], mp(u.f, counter+1)));
			}
		}
	}
	ld ans = INF;
	for (ll i=0; i<min(75, K+1); ++i) ans = min(ans, dist[H][i]);
	return ans;
}

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