oj.uz

Submission #1023235

# Submission time Handle Problem Language Result Execution time Memory
1023235 2024-07-14T13:52:21 Z nam6 Cyberland (APIO23_cyberland) C++17
100 / 100
 222 ms 107852 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std; 

vector<int> pouvoirs; 
vector<int> dejaVu;
set<int> zeroAccess; 
int fin;

struct Arc{
    int dest; 
    int poids; 
};
vector<vector<Arc>> adj;
 
struct Sit{
    int node; 
    int nbDiv; 
    double pow2; 
    double dis; 
    bool operator <(const Sit &other) const{
        return dis > other.dis; 
    }
};
 
void dfs(int n){
    if(dejaVu[n]) return; 
    dejaVu[n] = 1; 
    if(n == fin) return;
    if(pouvoirs[n] == 0) zeroAccess.insert(n);
        
    for(Arc arc : adj[n]){
        if(!dejaVu[arc.dest])
            dfs(arc.dest); 
    } 
}
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    
    pouvoirs = arr; 
    fin = H; 
    K = min(K, 70);

    dejaVu = vector<int>(N, 0);
    adj = vector<vector<Arc>>(N);

    for(int n=0; n<M; n++){
        adj[x[n]].push_back({y[n], c[n]}); 
        adj[y[n]].push_back({x[n], c[n]}); 
    }
    zeroAccess.clear(); 
    zeroAccess.insert(0);
    dfs(0);
    if(!dejaVu[fin]) return -1;  
 
    vector<vector<int>> deja(N, vector<int>(K+1)); 
    vector<vector<double>> distances(N, vector<double>(K+1, 1e17)); 
    distances[fin][0]=0;
    priority_queue<Sit> aTraiter; 
    aTraiter.push({fin, 0, 1, 0});

    while(!aTraiter.empty()){
        Sit curSit = aTraiter.top(); 
        aTraiter.pop(); 
        if(curSit.node == fin && curSit.nbDiv != 0) continue; 
        if(deja[curSit.node][curSit.nbDiv]) continue; 
        if(zeroAccess.count(curSit.node)) return curSit.dis; 
        deja[curSit.node][curSit.nbDiv] = 1; 

        for(Arc voisin : adj[curSit.node]){
            int v = voisin.dest; 
            int w = voisin.poids; 

            if( distances[curSit.node][curSit.nbDiv] + w/curSit.pow2 < distances[v][curSit.nbDiv]){
                distances[v][curSit.nbDiv] = distances[curSit.node][curSit.nbDiv] + w/curSit.pow2;
                aTraiter.push({v, curSit.nbDiv, curSit.pow2, distances[v][curSit.nbDiv]});
            }

            if(pouvoirs[v] == 2 && curSit.nbDiv < K){
                if(distances[curSit.node][curSit.nbDiv] + w/curSit.pow2 <  distances[v][curSit.nbDiv + 1]){
                    distances[v][curSit.nbDiv + 1] = distances[curSit.node][curSit.nbDiv] + w/curSit.pow2;
                    aTraiter.push({v, curSit.nbDiv+1, curSit.pow2*2, distances[v][curSit.nbDiv + 1]});
                }
            }        
        }
    }
    return -1; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 856 KB Correct.
2 Correct 13 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1624 KB Correct.
2 Correct 21 ms 2048 KB Correct.
3 Correct 18 ms 1884 KB Correct.
4 Correct 20 ms 1992 KB Correct.
5 Correct 23 ms 2036 KB Correct.
6 Correct 19 ms 6540 KB Correct.
7 Correct 23 ms 6280 KB Correct.
8 Correct 13 ms 11352 KB Correct.
9 Correct 22 ms 1368 KB Correct.
10 Correct 21 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1784 KB Correct.
2 Correct 22 ms 1760 KB Correct.
3 Correct 21 ms 1880 KB Correct.
4 Correct 23 ms 1368 KB Correct.
5 Correct 22 ms 1368 KB Correct.
6 Correct 5 ms 4952 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 32084 KB Correct.
2 Correct 26 ms 1888 KB Correct.
3 Correct 28 ms 1948 KB Correct.
4 Correct 26 ms 1972 KB Correct.
5 Correct 32 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1740 KB Correct.
2 Correct 22 ms 1848 KB Correct.
3 Correct 21 ms 1888 KB Correct.
4 Correct 20 ms 6212 KB Correct.
5 Correct 18 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1872 KB Correct.
2 Correct 17 ms 1832 KB Correct.
3 Correct 29 ms 9820 KB Correct.
4 Correct 14 ms 4372 KB Correct.
5 Correct 26 ms 1372 KB Correct.
6 Correct 23 ms 1828 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1860 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 55 ms 39244 KB Correct.
4 Correct 43 ms 11864 KB Correct.
5 Correct 43 ms 24952 KB Correct.
6 Correct 23 ms 11096 KB Correct.
7 Correct 51 ms 11032 KB Correct.
8 Correct 41 ms 3304 KB Correct.
9 Correct 18 ms 1908 KB Correct.
10 Correct 18 ms 1740 KB Correct.
11 Correct 46 ms 2768 KB Correct.
12 Correct 27 ms 1848 KB Correct.
13 Correct 19 ms 1896 KB Correct.
14 Correct 47 ms 14004 KB Correct.
15 Correct 38 ms 5576 KB Correct.
16 Correct 19 ms 1884 KB Correct.
17 Correct 22 ms 2132 KB Correct.
18 Correct 21 ms 1836 KB Correct.
19 Correct 39 ms 2916 KB Correct.
20 Correct 3 ms 600 KB Correct.
21 Correct 2 ms 604 KB Correct.
22 Correct 2 ms 1372 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2388 KB Correct.
2 Correct 4 ms 1372 KB Correct.
3 Correct 119 ms 107852 KB Correct.
4 Correct 58 ms 5892 KB Correct.
5 Correct 60 ms 41548 KB Correct.
6 Correct 25 ms 15964 KB Correct.
7 Correct 42 ms 20288 KB Correct.
8 Correct 48 ms 3484 KB Correct.
9 Correct 19 ms 2252 KB Correct.
10 Correct 20 ms 2076 KB Correct.
11 Correct 222 ms 1632 KB Correct.
12 Correct 21 ms 2332 KB Correct.
13 Correct 22 ms 2492 KB Correct.
14 Correct 71 ms 42320 KB Correct.
15 Correct 62 ms 52124 KB Correct.
16 Correct 44 ms 18488 KB Correct.
17 Correct 44 ms 5768 KB Correct.
18 Correct 18 ms 2508 KB Correct.
19 Correct 32 ms 2452 KB Correct.
20 Correct 23 ms 2336 KB Correct.
21 Correct 37 ms 3324 KB Correct.
22 Correct 3 ms 604 KB Correct.
23 Correct 2 ms 880 KB Correct.
24 Correct 3 ms 1884 KB Correct.