oj.uz

Submission #976511

# Submission time Handle Problem Language Result Execution time Memory
976511 2024-05-06T16:04:44 Z Marcus Cyberland (APIO23_cyberland) C++17
68 / 100
 279 ms 13396 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;}
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4444 KB Correct.
2 Correct 24 ms 4516 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4944 KB Correct.
2 Correct 100 ms 4440 KB Correct.
3 Correct 95 ms 4488 KB Correct.
4 Correct 103 ms 4504 KB Correct.
5 Correct 105 ms 4468 KB Correct.
6 Correct 145 ms 4952 KB Correct.
7 Correct 192 ms 5096 KB Correct.
8 Correct 82 ms 5712 KB Correct.
9 Correct 56 ms 4420 KB Correct.
10 Correct 55 ms 4432 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4440 KB Correct.
2 Correct 97 ms 4500 KB Correct.
3 Correct 88 ms 4948 KB Correct.
4 Correct 59 ms 4428 KB Correct.
5 Correct 59 ms 4444 KB Correct.
6 Correct 32 ms 5024 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 8660 KB Correct.
2 Correct 151 ms 4476 KB Correct.
3 Correct 130 ms 5472 KB Correct.
4 Correct 136 ms 5348 KB Correct.
5 Correct 81 ms 5408 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4584 KB Correct.
2 Correct 52 ms 4444 KB Correct.
3 Correct 56 ms 4540 KB Correct.
4 Correct 106 ms 5424 KB Correct.
5 Correct 34 ms 4444 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4572 KB Correct.
2 Correct 43 ms 4444 KB Correct.
3 Correct 32 ms 9308 KB Correct.
4 Correct 63 ms 5016 KB Correct.
5 Correct 42 ms 4440 KB Correct.
6 Correct 52 ms 4444 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4488 KB Correct.
2 Correct 15 ms 4700 KB Correct.
3 Incorrect 279 ms 13396 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 4440 KB Correct.
2 Correct 28 ms 4696 KB Correct.
3 Correct 166 ms 13140 KB Correct.
4 Incorrect 228 ms 7248 KB Wrong Answer.
5 Halted 0 ms 0 KB -