oj.uz

Submission #777314

# Submission time Handle Problem Language Result Execution time Memory
777314 2023-07-09T04:02:27 Z yeyso Cyberland (APIO23_cyberland) C++17
21 / 100
 41 ms 13440 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>


double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {

    vector<vector<long long>> adj(N, vector<long long>());

    vector<vector<long long>> dma(N, vector<long long>());
    for(long long i = 0; i < M; i ++){
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);

        dma[x[i]].push_back(c[i]);
        dma[y[i]].push_back(c[i]);
    }
    queue<pair<long long, long long>> q;
    q.push({0, H});
    vector<long long> v(N, 0);
    vector<long long> d(N, LONG_LONG_MAX / 2);
    d[H] = 0;
    long long node, dist;
    while(!q.empty()){
        node = q.front().second;
        dist = q.front().first;
        q.pop();
        if(!v[node]){
            v[node] = 1;
            for(long long i = 0; i < adj[node].size(); i ++){
                d[adj[node][i]] = min(d[adj[node][i]], d[node] + dma[node][i]);
                q.push({dist + dma[node][i], adj[node][i]});
            }
        }
    }
    q.push({0, 0});
    vector<long long> v2(N, 0);
    v2[H] = 1;
    while(!q.empty()){
        node = q.front().second;
        q.pop();
        if(!v2[node]){
            v2[node] = 1;
            for(long long i = 0; i < adj[node].size(); i ++){
                q.push({0, adj[node][i]});
            }
        }
    }
    long long lowest = d[0];
    for(long long i = 0; i < d.size(); i ++){
        if(d[i] < lowest and v2[i] == 1 and arr[i] == 0){
            lowest = d[i];
        }
    }
    if(d[0] >= LONG_LONG_MAX / 2) return -1;
    if(lowest >= LONG_LONG_MAX / 2) return -1;
    return lowest;



}
/*
g++ -std=gnu++17 -O2 -Wall -pipe -static -o cyberland stub.cpp cyberland.cpp
1
10 9 10
6
1 1 0 1 2 2 1 0 2 1
0 1 3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

1
3 2 30
2
1 0 1
1 2 12
2 0 4
*/

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:31:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
cyberland.cpp:45:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(long long i = 0; i < adj[node].size(); i ++){
      |                                  ~~^~~~~~~~~~~~~~~~~~
cyberland.cpp:51:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(long long i = 0; i < d.size(); i ++){
      |                          ~~^~~~~~~~~~

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 496 KB Correct.
2 Correct 25 ms 536 KB Correct.
3 Correct 24 ms 476 KB Correct.
4 Correct 33 ms 468 KB Correct.
5 Correct 31 ms 468 KB Correct.
6 Correct 21 ms 2108 KB Correct.
7 Correct 27 ms 2032 KB Correct.
8 Correct 12 ms 3808 KB Correct.
9 Correct 26 ms 436 KB Correct.
10 Correct 25 ms 424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 476 KB Correct.
2 Correct 24 ms 532 KB Correct.
3 Correct 23 ms 468 KB Correct.
4 Correct 26 ms 420 KB Correct.
5 Correct 26 ms 428 KB Correct.
6 Correct 5 ms 1744 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 528 KB Correct.
2 Correct 21 ms 540 KB Correct.
3 Correct 41 ms 13440 KB Correct.
4 Correct 15 ms 1520 KB Correct.
5 Incorrect 25 ms 408 KB Wrong Answer.
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 452 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 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -