제출 #749892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749892		Cyber_Wolf	Cyberland (APIO23_cyberland)	C++17	100 / 100	2561 ms	177224 KiB

cyberland

#include "cyberland.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#include <vector>
#pragma GCC optimize("Ofast")
#define lg long long
#define ld long double
#define ff first
#define sf second
using namespace std;

const lg N = 1e5+5, K = 71;

ld dist[N][K];
lg in_queue[N][K];
vector<array<lg, 2>> adj[N];


double solve(int n, int m, int k, int h, std::vector<int> g, std::vector<int> r, std::vector<int> d, std::vector<int> t) 
{
k = min(k, 70);
	for(int i = 0; i < n; i++)	adj[i].clear();
    for(int i = 0; i < m; i++)
    {
    	adj[g[i]].push_back({r[i], d[i]});
    	adj[r[i]].push_back({g[i], d[i]});
    }
	adj[h].clear();
    for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j <= k; j++)
    	{
    		dist[i][j] = 1e18;
    		in_queue[i][j] = 0;
    	}
    }
    dist[0][k] = 0;
    priority_queue<pair<ld, lg>> pq[71];
    pq[k].push({-dist[0][k], 0});
    in_queue[0][k] = 1;
    for(int i = k; i >= 0; i--)
    {
	    while(pq[i].size())
	    {
	    	pair<ld, lg> p = pq[i].top();
	    	pq[i].pop();
	    	in_queue[p.sf][i] = 0;
	    	for(auto [it, c] : adj[p.sf])
	    	{
	    		ld cost = dist[p.sf][i]+c;
	    		if(t[it] == 0)	cost = 0;
	    		if(t[it] == 2 && i > 0 && dist[it][i-1] > (cost)/2.0)
	    		{
	    			dist[it][i-1] = cost/2.0;
	    			if(!in_queue[it][i-1])pq[i-1].push({-dist[it][i-1], it});
	    			in_queue[it][i-1] = true;
	    		}
	    		if(dist[it][i] > cost)
	    		{
	    			dist[it][i] = cost;
	    			if(!in_queue[it][i])pq[i].push({-dist[it][i], it});
	    			in_queue[it][i] = true;
	    		}
	    	}
	    }
    }
    ld ans = 1e18;
    for(int i = 0; i <= k; i++)
    {
    	ans = min(ans, dist[h][i]);
    }
    if(ans > 1e15)
    {
    	ans = -1;	
    }
    return ans;
}

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