oj.uz

Submission #1023114

# Submission time Handle Problem Language Result Execution time Memory
1023114 2024-07-14T09:49:24 Z clemmy14 Cyberland (APIO23_cyberland) C++17
100 / 100
 225 ms 83792 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
//#define int long long
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, 1e17)); 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 16 ms 856 KB Correct.
2 Correct 15 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1628 KB Correct.
2 Correct 27 ms 1900 KB Correct.
3 Correct 39 ms 1876 KB Correct.
4 Correct 26 ms 1744 KB Correct.
5 Correct 31 ms 1920 KB Correct.
6 Correct 22 ms 5596 KB Correct.
7 Correct 28 ms 5316 KB Correct.
8 Correct 17 ms 9404 KB Correct.
9 Correct 25 ms 1452 KB Correct.
10 Correct 27 ms 1220 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1816 KB Correct.
2 Correct 32 ms 1872 KB Correct.
3 Correct 40 ms 1704 KB Correct.
4 Correct 30 ms 1384 KB Correct.
5 Correct 27 ms 1472 KB Correct.
6 Correct 6 ms 4188 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28080 KB Correct.
2 Correct 38 ms 1840 KB Correct.
3 Correct 46 ms 1916 KB Correct.
4 Correct 31 ms 1920 KB Correct.
5 Correct 42 ms 1472 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1724 KB Correct.
2 Correct 21 ms 1920 KB Correct.
3 Correct 36 ms 1900 KB Correct.
4 Correct 32 ms 5312 KB Correct.
5 Correct 19 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1880 KB Correct.
2 Correct 19 ms 1560 KB Correct.
3 Correct 30 ms 9332 KB Correct.
4 Correct 15 ms 3752 KB Correct.
5 Correct 21 ms 1312 KB Correct.
6 Correct 23 ms 1884 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1880 KB Correct.
2 Correct 4 ms 860 KB Correct.
3 Correct 62 ms 36048 KB Correct.
4 Correct 51 ms 10832 KB Correct.
5 Correct 48 ms 21712 KB Correct.
6 Correct 26 ms 9976 KB Correct.
7 Correct 56 ms 9760 KB Correct.
8 Correct 64 ms 3236 KB Correct.
9 Correct 24 ms 1788 KB Correct.
10 Correct 20 ms 1636 KB Correct.
11 Correct 48 ms 2624 KB Correct.
12 Correct 23 ms 1764 KB Correct.
13 Correct 21 ms 1844 KB Correct.
14 Correct 49 ms 14144 KB Correct.
15 Correct 48 ms 5400 KB Correct.
16 Correct 21 ms 1808 KB Correct.
17 Correct 24 ms 1956 KB Correct.
18 Correct 22 ms 1712 KB Correct.
19 Correct 59 ms 2916 KB Correct.
20 Correct 3 ms 604 KB Correct.
21 Correct 3 ms 604 KB Correct.
22 Correct 3 ms 1184 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2104 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 97 ms 83792 KB Correct.
4 Correct 44 ms 4956 KB Correct.
5 Correct 45 ms 32848 KB Correct.
6 Correct 25 ms 13148 KB Correct.
7 Correct 44 ms 15400 KB Correct.
8 Correct 52 ms 3444 KB Correct.
9 Correct 29 ms 1968 KB Correct.
10 Correct 20 ms 1860 KB Correct.
11 Correct 225 ms 1624 KB Correct.
12 Correct 25 ms 2016 KB Correct.
13 Correct 23 ms 2208 KB Correct.
14 Correct 53 ms 32960 KB Correct.
15 Correct 58 ms 39712 KB Correct.
16 Correct 52 ms 14636 KB Correct.
17 Correct 46 ms 4708 KB Correct.
18 Correct 19 ms 2092 KB Correct.
19 Correct 29 ms 2224 KB Correct.
20 Correct 24 ms 2032 KB Correct.
21 Correct 41 ms 3248 KB Correct.
22 Correct 3 ms 600 KB Correct.
23 Correct 4 ms 860 KB Correct.
24 Correct 5 ms 1624 KB Correct.