oj.uz

Submission #1021413

# Submission time Handle Problem Language Result Execution time Memory
1021413 2024-07-12T17:45:18 Z Arturgo Cyberland (APIO23_cyberland) C++17
5 / 100
 34 ms 28236 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, 1e9)); 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);

    double best = 1e9;
 
    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;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:50:12: warning: unused variable 'best' [-Wunused-variable]
   50 |     double best = 1e9;
      |            ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1624 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1820 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 28236 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1704 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1820 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1820 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2088 KB Wrong Answer.
2 Halted 0 ms 0 KB -