oj.uz

Submission #1021418

# Submission time Handle Problem Language Result Execution time Memory
1021418 2024-07-12T17:48:34 Z Arturgo Cyberland (APIO23_cyberland) C++17
100 / 100
 238 ms 83796 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
 
int dest;
set<int> posEnd;
vector<bool> visited1;
vector<int> type;
vector<vector<pair<int, int>>> adj;
 
void dfs(int node) {
    if(visited1[node]) return;
    visited1[node]=true;
    if(node == dest) return;
    if(type[node] == 0) posEnd.insert(node);
    for(auto child : adj[node]) if(!visited1[child.first]) {
        dfs(child.first);
    }
}
 
struct in {
    double dis, divPow;
    int nbdiv, node;
    bool operator< (const in& other) const {
        return dis > other.dis;
    }
};
 
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 70);
    dest=H;
    type = arr;
    visited1 = vector<bool>(N, false);
    adj = vector<vector<pair<int, int>>>(N);
    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]});
    }
    posEnd.clear();
    posEnd.insert(0);
    dfs(0);
    if(!visited1[H]) return -1;
 
    vector<vector<bool>> visited(N, vector<bool>(K + 1, false)); 
    vector<vector<double>> distance(N, vector<double>(K + 1, 1e20)); distance[H][0]=0;
    priority_queue<in> q; 
    in st; st.dis=0; st.divPow=1; st.nbdiv=0; st.node=H;
    q.push(st);

    while(!q.empty()) {
        in cur = q.top(); q.pop(); 
        if(cur.node == H && cur.nbdiv != 0) continue;
        if(visited[cur.node][cur.nbdiv]) continue;
        if(posEnd.count(cur.node)) return cur.dis;
        visited[cur.node][cur.nbdiv]=true;
        for(auto [child, childDis] : adj[cur.node]) {
            // not dividing by 2
            if(distance[cur.node][cur.nbdiv]+childDis/cur.divPow < distance[child][cur.nbdiv]) {
                distance[child][cur.nbdiv] = distance[cur.node][cur.nbdiv]+childDis/cur.divPow;
                in newV;
                newV.dis=distance[child][cur.nbdiv]; newV.node=child;
                newV.divPow=cur.divPow; newV.nbdiv=cur.nbdiv; 
                q.push(newV);
            }
            // dividing by 2
            if(type[child] == 2 && cur.nbdiv+1 <= K && distance[cur.node][cur.nbdiv]+childDis/cur.divPow < distance[child][cur.nbdiv+1]) {
                distance[child][cur.nbdiv+1] = distance[cur.node][cur.nbdiv]+childDis/cur.divPow;
                in newV;
                newV.dis=distance[child][cur.nbdiv+1]; newV.node=child;
                newV.divPow=cur.divPow*2; newV.nbdiv=cur.nbdiv+1; 
                q.push(newV);
            }
        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1624 KB Correct.
2 Correct 26 ms 1932 KB Correct.
3 Correct 32 ms 1760 KB Correct.
4 Correct 36 ms 1904 KB Correct.
5 Correct 25 ms 1992 KB Correct.
6 Correct 22 ms 5596 KB Correct.
7 Correct 26 ms 5420 KB Correct.
8 Correct 13 ms 9308 KB Correct.
9 Correct 25 ms 1444 KB Correct.
10 Correct 24 ms 1368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1568 KB Correct.
2 Correct 25 ms 1872 KB Correct.
3 Correct 24 ms 1880 KB Correct.
4 Correct 27 ms 1292 KB Correct.
5 Correct 27 ms 1372 KB Correct.
6 Correct 7 ms 4188 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 27740 KB Correct.
2 Correct 31 ms 1980 KB Correct.
3 Correct 31 ms 1920 KB Correct.
4 Correct 31 ms 1888 KB Correct.
5 Correct 37 ms 1368 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1632 KB Correct.
2 Correct 22 ms 1884 KB Correct.
3 Correct 21 ms 1828 KB Correct.
4 Correct 24 ms 5240 KB Correct.
5 Correct 19 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1624 KB Correct.
2 Correct 18 ms 1780 KB Correct.
3 Correct 30 ms 9468 KB Correct.
4 Correct 14 ms 3752 KB Correct.
5 Correct 21 ms 1380 KB Correct.
6 Correct 20 ms 1884 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1580 KB Correct.
2 Correct 3 ms 856 KB Correct.
3 Correct 63 ms 36084 KB Correct.
4 Correct 49 ms 10832 KB Correct.
5 Correct 42 ms 21488 KB Correct.
6 Correct 26 ms 10016 KB Correct.
7 Correct 44 ms 9832 KB Correct.
8 Correct 46 ms 3308 KB Correct.
9 Correct 18 ms 1816 KB Correct.
10 Correct 24 ms 1652 KB Correct.
11 Correct 47 ms 2576 KB Correct.
12 Correct 20 ms 1772 KB Correct.
13 Correct 20 ms 1840 KB Correct.
14 Correct 47 ms 14148 KB Correct.
15 Correct 44 ms 5360 KB Correct.
16 Correct 20 ms 1868 KB Correct.
17 Correct 29 ms 2084 KB Correct.
18 Correct 21 ms 1712 KB Correct.
19 Correct 45 ms 2828 KB Correct.
20 Correct 2 ms 604 KB Correct.
21 Correct 2 ms 604 KB Correct.
22 Correct 3 ms 1224 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1820 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 96 ms 83796 KB Correct.
4 Correct 49 ms 4956 KB Correct.
5 Correct 56 ms 32876 KB Correct.
6 Correct 26 ms 13140 KB Correct.
7 Correct 46 ms 15396 KB Correct.
8 Correct 49 ms 3144 KB Correct.
9 Correct 19 ms 1964 KB Correct.
10 Correct 19 ms 1848 KB Correct.
11 Correct 238 ms 1636 KB Correct.
12 Correct 20 ms 2016 KB Correct.
13 Correct 20 ms 2212 KB Correct.
14 Correct 52 ms 32852 KB Correct.
15 Correct 61 ms 39624 KB Correct.
16 Correct 47 ms 14644 KB Correct.
17 Correct 45 ms 4704 KB Correct.
18 Correct 19 ms 2080 KB Correct.
19 Correct 22 ms 2228 KB Correct.
20 Correct 21 ms 2112 KB Correct.
21 Correct 40 ms 3168 KB Correct.
22 Correct 2 ms 604 KB Correct.
23 Correct 2 ms 860 KB Correct.
24 Correct 3 ms 1628 KB Correct.