Submission #976511

#	Time	Username	Problem	Language	Result	Execution time	Memory
976511		Marcus	Cyberland (APIO23_cyberland)	C++17	68 / 100	279 ms	13396 KiB

cyberland

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

double const INF = 1e105;
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 z=0; z<number; z++) {processed[z] = false;}
    dist[0] = 0;
    for (int z = 0; z<number; z++) if (dist[z] < INF) q.push({-dist[z], z});
    while (!q.empty()) 
	{
        int a = q.top().second; q.pop();
        if (processed[a] || a == target) 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, 67);
    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: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3