oj.uz

Submission #980593

# Submission time Handle Problem Language Result Execution time Memory
980593 2024-05-12T09:09:19 Z SirLemonMeringue Cyberland (APIO23_cyberland) C++17
100 / 100
 290 ms 14408 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100010
#define INF 1e303

#include <vector>

vector<pair<int,int>> adj[MAX_N];
bool reachable[MAX_N];
double dist[MAX_N];

void dfs(int node, int specialNode){
    reachable[node] = true;
    if (node!=specialNode){
        for(auto a : adj[node]){
            if (!reachable[a.first]){
                dfs(a.first,specialNode);
            }
        }
    }
}

struct P {
    int dest;
    double dist;
    bool moved = true;
    bool operator< (P other) const {
        return dist > other.dist;
    }
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    //clear all adjacency lists and reachables and best dist
    for(int i=0;i<N;i++) adj[i].clear(), reachable[i]=false, dist[i]=INF;

    //remake all adjacencies
    for(int i=0;i<M;i++){
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }

    //run dfs to find all reachable nodes
    dfs(0,H);

    //if unreachable return
    if (!reachable[H]) return -1;
    reachable[H] = false;

    //run base dijkstra, sourced at reachable 0s and start
    priority_queue<P> todo;
    todo.push({0,0});
    for(int i=0;i<N;i++){
        if (reachable[i] && arr[i]==0){
            todo.push({i,0});
        }
    }

    while(!todo.empty()){
        P u = todo.top();
        todo.pop();
        if (u.dist < dist[u.dest]){
            dist[u.dest] = u.dist;
            if (u.dest != H){
                for(auto a : adj[u.dest]){
                    if (u.dist + a.second < dist[a.first]){
                        todo.push({a.first,u.dist+a.second});
                    }
                }
            }
        }
    }

    //printf("%lf %lf %lf\n",dist[0],dist[1],dist[2]);

    //run at most K further dijkstras, sourced at reachable 0s and reachable doubles (using half of best dist)
    for(int k=1;k<=K;k++){
        bool changed = false;
        //todo is already empty, so just add to it
        for(int i=0;i<N;i++){
            if (reachable[i]){
                if (arr[i]==0){
                    todo.push({i,0});
                    //printf("%d %lf\n",i,0);
                } else if (arr[i]==2){
                    todo.push({i,dist[i]/2,false});
                    //printf("%d %lf\n",i,dist[i]/2);
                }
            }
        }

        while(!todo.empty()){
            P u = todo.top();
            todo.pop();
            if (u.dist < dist[u.dest]){
                if (u.moved){
                    changed = true;
                    dist[u.dest] = u.dist;
                }
                if (u.dest != H){
                    for(auto a : adj[u.dest]){
                        if (u.dist + a.second < dist[a.first]){
                            todo.push({a.first,u.dist+a.second});
                        }
                    }
                }
            }
        }
        if (!changed) break;
    }
    
    return dist[H];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3536 KB Correct.
2 Correct 14 ms 3932 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3676 KB Correct.
2 Correct 20 ms 3644 KB Correct.
3 Correct 19 ms 3420 KB Correct.
4 Correct 20 ms 3420 KB Correct.
5 Correct 19 ms 3676 KB Correct.
6 Correct 17 ms 4184 KB Correct.
7 Correct 22 ms 4164 KB Correct.
8 Correct 10 ms 4956 KB Correct.
9 Correct 19 ms 3420 KB Correct.
10 Correct 18 ms 3568 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3664 KB Correct.
2 Correct 23 ms 3672 KB Correct.
3 Correct 21 ms 3676 KB Correct.
4 Correct 22 ms 3420 KB Correct.
5 Correct 22 ms 3416 KB Correct.
6 Correct 6 ms 4632 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7956 KB Correct.
2 Correct 63 ms 4692 KB Correct.
3 Correct 56 ms 4432 KB Correct.
4 Correct 60 ms 4436 KB Correct.
5 Correct 42 ms 4436 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3676 KB Correct.
2 Correct 20 ms 3672 KB Correct.
3 Correct 19 ms 3676 KB Correct.
4 Correct 24 ms 4764 KB Correct.
5 Correct 17 ms 3416 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3676 KB Correct.
2 Correct 18 ms 3756 KB Correct.
3 Correct 30 ms 8792 KB Correct.
4 Correct 18 ms 4556 KB Correct.
5 Correct 20 ms 3420 KB Correct.
6 Correct 19 ms 3712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3888 KB Correct.
2 Correct 11 ms 3928 KB Correct.
3 Correct 121 ms 12884 KB Correct.
4 Correct 124 ms 7500 KB Correct.
5 Correct 172 ms 11980 KB Correct.
6 Correct 68 ms 10708 KB Correct.
7 Correct 117 ms 7568 KB Correct.
8 Correct 90 ms 5720 KB Correct.
9 Correct 43 ms 4692 KB Correct.
10 Correct 40 ms 4436 KB Correct.
11 Correct 88 ms 5456 KB Correct.
12 Correct 49 ms 4692 KB Correct.
13 Correct 48 ms 4688 KB Correct.
14 Correct 95 ms 8784 KB Correct.
15 Correct 93 ms 6476 KB Correct.
16 Correct 44 ms 4688 KB Correct.
17 Correct 56 ms 4688 KB Correct.
18 Correct 48 ms 4692 KB Correct.
19 Correct 149 ms 5564 KB Correct.
20 Correct 4 ms 3420 KB Correct.
21 Correct 4 ms 3672 KB Correct.
22 Correct 6 ms 4444 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3724 KB Correct.
2 Correct 13 ms 3932 KB Correct.
3 Correct 125 ms 14408 KB Correct.
4 Correct 110 ms 6164 KB Correct.
5 Correct 290 ms 11980 KB Correct.
6 Correct 103 ms 10812 KB Correct.
7 Correct 131 ms 9048 KB Correct.
8 Correct 107 ms 5636 KB Correct.
9 Correct 70 ms 4688 KB Correct.
10 Correct 59 ms 4608 KB Correct.
11 Correct 210 ms 4796 KB Correct.
12 Correct 75 ms 4636 KB Correct.
13 Correct 71 ms 4612 KB Correct.
14 Correct 221 ms 10988 KB Correct.
15 Correct 237 ms 9220 KB Correct.
16 Correct 153 ms 7120 KB Correct.
17 Correct 112 ms 5716 KB Correct.
18 Correct 64 ms 4736 KB Correct.
19 Correct 85 ms 4748 KB Correct.
20 Correct 72 ms 4692 KB Correct.
21 Correct 221 ms 5680 KB Correct.
22 Correct 7 ms 3420 KB Correct.
23 Correct 6 ms 3672 KB Correct.
24 Correct 8 ms 4444 KB Correct.