Submission #924908

#	Time	Username	Problem	Language	Result	Execution time	Memory
924908		pan	사이버랜드 (APIO23_cyberland)	C++17	39 / 100	322 ms	11464 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<ld, ll> pd2;
typedef pair<string, ll> psi;
typedef pair<ll, ll> pi;
typedef pair<ld, pi> pdi;
const long double INF = 1e18;
vector<pd> adj[100005];
bool reachable[100005];
struct compare
{
	bool operator() (pd2 const&  a, pd2 const&  b)
	{
		return a.f>b.f; // least element come out first
	}
};
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)
{
	ld ans = INF;
	ll n = N;
	for (ll i=0; i<N; ++i) {adj[i].clear(); adj[i].resize(0); reachable[i] = 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]));
	}
 
	
	vector<ld> dist(n+5, INF);
	dist[0] = 0.0; 
	for (ll i=min(80, K); i>=0; --i)
	{
		priority_queue<pd2, vector<pd2>, compare> pq;
		vector<ld> newdist(n+5, INF);
		vector<bool> visited(n+5, false);
		for (ll j=0; j<n; ++j) if (dist[j]!=INF) {pq.push(mp(dist[j], j));}
		while (pq.size())
		{
			ll city = pq.top().s;
			pq.pop();
			if (visited[city]) continue;
			visited[city] = true;
			if (city==H) continue;
			for (pd u: adj[city])
			{
				if (arr[u.f]==0 && dist[u.f]>0.0) 
				{
					dist[u.f] = 0.0;
					pq.push(mp(0.0, u.f));
				}
				if ((ld) dist[city]+ (ld) u.s<dist[u.f]) 
				{
					dist[u.f] = dist[city]+ (ld) u.s;
					pq.push(mp(dist[u.f], u.f));
				}
				if (arr[u.f]==2 && i>0 && ((ld) dist[city]+ (ld) u.s)/2.0 < newdist[u.f])
				{
					newdist[u.f] = ((ld) dist[city]+ (ld) u.s)/2.0;
				}
 
			}
		}
		ans = min(ans, dist[H]);
		swap(dist, newdist);
	}
 
	return (ans==INF)?-1: ans;
}

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