oj.uz

Submission #64069

# Submission time Handle Problem Language Result Execution time Memory
64069 2018-08-03T09:53:13 Z zubec Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 12 ms 7420 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 100100;

vector <pair<int, int> > g[N];

int n, pr[N];

long long d[N];

map<int, int> blockd[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    for (int i = 0; i < M; i++){
        int u = R[i][0]+1, v = R[i][1]+1;
        g[u].push_back({v, L[i]});
        g[v].push_back({u, L[i]});
    }
    set<pair<long long, int> > q;
    for (int i = 1; i <= n; i++)
        d[i] = 1e15;
    for (int i = 0; i < K; i++){
        int v = P[i]+1;
        d[v] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].first, len = g[v][i].second;
            if (d[v] + len < d[to]){
                q.erase({d[to], to});
                d[to] = d[v]+len;
                pr[to] = v;
                q.insert({d[to], to});
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (pr[i] != 0){
            blockd[pr[i]][i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        d[i] = 1e15;
    for (int i = 0; i < K; i++){
        int v = P[i]+1;
        d[v] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].first, len = g[v][i].second;
            if (blockd[v].find(to) != blockd[v].end())
                continue;
            if (d[v] + len < d[to]){
                q.erase({d[to], to});
                d[to] = d[v]+len;
                pr[to] = v;
                q.insert({d[to], to});
            }
        }
    }
    if (d[1] == 1e15)
        d[1] = -1;
    return d[1];

}

/**

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14

*/

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~
crocodile.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7420 KB Output isn't correct
2 Halted 0 ms 0 KB -