oj.uz

Submission #783377

# Submission time Handle Problem Language Result Execution time Memory
783377 2023-07-14T22:05:49 Z thimote75 Cyberland (APIO23_cyberland) C++17
0 / 100
 34 ms 8392 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;
using bdata = vector<bool>;
using ddata = vector<double>;
using idata = vector<int>;
using pii   = pair<int, int>;
using vpii  = vector<pii>;
using gpii  = vector<vpii>;

template<typename U, typename V>
using pq = priority_queue<pair<U, V>>;

const double INF = 1e18;

int N, M, K;
int H;

bdata reachable;

gpii roads;
idata type;

void dfs_reach (int node) {
    if (reachable[node]) return ;
    reachable[node] = true;

    for (const auto &road : roads[node])
        dfs_reach(road.first);
}

void dijkstra (ddata &distances, int H) {
    pq<double, int> queue;
    for (int i = 0; i < distances.size(); i ++)
        if (distances[i] != INF)
            queue.push({ - distances[i], i });
    
    while (queue.size() != 0) {
        const auto curr = queue.top(); queue.pop();

        double dist = - curr.first;
        int node = curr.second;

        if (node == H) continue ;
        if (distances[node] != dist) continue ;

        for (const auto &road : roads[node]) {
            int next  = road.first;
            int ndist = road.second + dist;
            if (ndist >= distances[next]) continue ;

            distances[next] = ndist;
            queue.push({ - ndist, next });
        }
    }
}
void divide (int N, ddata &distances) {
    ddata new_distances(N);
    for (int i = 0; i < N; i ++) new_distances[i] = distances[i];

    for (int i = 0; i < N; i ++) {
        if (!(type[i] == 2 && reachable[i])) continue ;

        for (const auto &road : roads[i]) {
            double h = (distances[i] / 2.0) + road.second;

            new_distances[road.first] = min(
                new_distances[road.first],
                h
            );
        }
    }

    for (int i = 0; i < N; i ++) distances[i] = new_distances[i];
}

ddata create (int N) {
    ddata res(N, INF);
    for (int i = 0; i < N; i ++)
        if (reachable[i] && type[i] == 0)
            res[i] = 0;
    return res;
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    type.clear(); type.resize(N);
    for (int i = 0; i < N; i ++) type[i] = arr[i];
    type[0] = 0;

    roads.clear(); roads.resize(N);
    for (int i = 0; i < M; i ++) {
        roads[x[i]].push_back({ y[i], c[i] });
        roads[y[i]].push_back({ x[i], c[i] });
    }

    reachable.clear(); reachable.resize(N, false);
    dfs_reach(0);
    if (!reachable[H]) return -1;

    ddata values = create(N);
    dijkstra(values, H);
    //for (int i = 0; i < K; i ++) {
    //    divide(N, values);
    //    dijkstra(values, H);
    //}

    return values[H];
}

Compilation message

cyberland.cpp: In function 'void dijkstra(ddata&, int)':
cyberland.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < distances.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 456 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 8392 KB Double -2.14748e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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