Submission #976506

#	Time	Username	Problem	Language	Result	Execution time	Memory
976506		Marcus	Cyberland (APIO23_cyberland)	C++17	15 / 100	356 ms	8660 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

double const INF = 1e15;
int const N = 1e5;
vector<vector<pair<int, int>>> adj(N);
vector<double> dist(N);
vector<double> dist2(N);
vector<bool> processed(N);
priority_queue<pair<double, int>> q;
double answer = INF;

void dijkstra(int number, int target)
{
    for (int j=0; j<number; j++) {processed[j] = false;}
    dist[0] = 0;
    for (int j = 0; j<number; j++) if (dist[j] < INF) q.push({-dist[j], j});
    while (!q.empty()) 
	{
        int a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (auto u : adj[a]) 
	    {
            int b = u.first, w = u.second;
            if (dist[a]+w < dist[b]) 
		    {
                dist[b] = dist[a]+w;
                q.push({-dist[b],b});
            }
        }
    }
    answer = min(answer, dist[target]);
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    answer = INF;
    for(int i = 0; i < n; i++) adj[i].clear();
    for (int i=0; i<m; i++)
	{
		int v = x[i]; int u = y[i]; int w = c[i];
        adj[v].push_back({u, w});
        adj[u].push_back({v, w});
	}

    for (int i=0; i<n; i++) {dist[i] = INF;}
    dijkstra(n, h);
    if (dist[h] == INF) {return -1;}
    for (int i=0; i<n; i++) {if (dist[i] != INF) dist[i] = (arr[i] ? INF : 0);}

    k = min(k, 65);
    for (int i=1; i<=k; i++)
    {
        dijkstra(n, h);
        for (int j=0; j<n; j++) {dist2[j] = INF;}
        for (int j=0; j<n; j++)
        {
            if (arr[j] == 2) {
                for (auto p: adj[j]) {
                    int u = p.first; int w = p.second; 
                    dist2[u] = min(dist2[u], dist[j]/2+w);
                }
            }
        }
        for (int j=0; j<n; j++) {dist[j] = dist2[j];}
    }  

	return answer;
}

• 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