Submission #749891

#	Time	Username	Problem	Language	Result	Execution time	Memory
749891		Cyber_Wolf	Cyberland (APIO23_cyberland)	C++17	97 / 100	3071 ms	177240 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.first
#define ss second.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, pair<lg, lg>>> pq;
    pq.push({-dist[0][k], {0, k}});
    in_queue[0][k] = 1;
    while(pq.size())
    {
    	pair<ld, pair<lg, lg>> p = pq.top();
    	pq.pop();
    	in_queue[p.sf][p.ss] = 0;
    	for(auto [it, c] : adj[p.sf])
    	{
    		ld cost = dist[p.sf][p.ss]+c;
    		if(t[it] == 0)	cost = 0;
    		if(t[it] == 2 && p.ss > 0 && dist[it][p.ss-1] > (cost)/2.0)
    		{
    			dist[it][p.ss-1] = cost/2.0;
    			if(!in_queue[it][p.ss-1])pq.push({-dist[it][p.ss-1], {it,  p.ss-1}});
    			in_queue[it][p.ss-1] = true;
    		}
    		if(dist[it][p.ss] > cost)
    		{
    			dist[it][p.ss] = cost;
    			if(!in_queue[it][p.ss])pq.push({-dist[it][p.ss], {it,  p.ss}});
    			in_queue[it][p.ss] = 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: 0 / 3