oj.uz

Submission #976523

# Submission time Handle Problem Language Result Execution time Memory
976523 2024-05-06T16:18:49 Z Marcus Cyberland (APIO23_cyberland) C++17
68 / 100
 278 ms 11048 KB 
#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;}
    dist[0] = 0; dijkstra(n, h);
    if (dist[h] >= INF) {return -1;}
    for (int i=0; i<n; i++) {if (dist[i] != INF) dist[i] = ((arr[i] && 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4444 KB Correct.
2 Correct 18 ms 4504 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4444 KB Correct.
2 Correct 29 ms 4516 KB Correct.
3 Correct 28 ms 4440 KB Correct.
4 Correct 29 ms 4444 KB Correct.
5 Correct 29 ms 4440 KB Correct.
6 Correct 27 ms 5116 KB Correct.
7 Correct 34 ms 4956 KB Correct.
8 Correct 16 ms 5720 KB Correct.
9 Correct 27 ms 4428 KB Correct.
10 Correct 30 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4444 KB Correct.
2 Correct 30 ms 4440 KB Correct.
3 Correct 29 ms 4484 KB Correct.
4 Correct 30 ms 4188 KB Correct.
5 Correct 30 ms 4444 KB Correct.
6 Correct 8 ms 4956 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 8652 KB Correct.
2 Correct 144 ms 4500 KB Correct.
3 Correct 131 ms 4440 KB Correct.
4 Correct 135 ms 4460 KB Correct.
5 Correct 80 ms 4428 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4444 KB Correct.
2 Correct 23 ms 4440 KB Correct.
3 Correct 25 ms 4440 KB Correct.
4 Correct 25 ms 5192 KB Correct.
5 Correct 23 ms 4444 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4444 KB Correct.
2 Correct 21 ms 4608 KB Correct.
3 Correct 32 ms 9304 KB Correct.
4 Correct 17 ms 4952 KB Correct.
5 Correct 23 ms 4444 KB Correct.
6 Correct 23 ms 4444 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4544 KB Correct.
2 Correct 17 ms 4440 KB Correct.
3 Incorrect 278 ms 11048 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4544 KB Correct.
2 Correct 27 ms 4440 KB Correct.
3 Correct 188 ms 10624 KB Correct.
4 Incorrect 231 ms 4936 KB Wrong Answer.
5 Halted 0 ms 0 KB -