oj.uz

Submission #72586

# Submission time Handle Problem Language Result Execution time Memory
72586 2018-08-26T10:26:39 Z Bruteforceman Crocodile's Underground City (IOI11_crocodile) C++11
0 / 100
 259 ms 248340 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const long long inf = 1e15;

struct data {
    int node;
    long long dist;
    data (int node, long long dist) {
        this -> node = node;
        this -> dist = dist;
    }
    data ( ) {}
    bool operator < (data x) const {
        return dist > x.dist;
    }
};

vector <int> g[100010];
vector <int> c[100010];
long long d[100010][2];
bool vis[100010];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    // freopen("in.txt", "r", stdin);

    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= m; i++) {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
        g[p].push_back(q);
        g[q].push_back(p);
        c[p].push_back(r);
        c[q].push_back(r);
    }
    for(int i = 0; i < n; i++) {
        d[i][0] = d[i][1] = inf;
    }

    priority_queue <data> Q;
    for(int i = 0; i < k; i++) {
        int x;
        scanf("%d", &x);
        d[x][1] = d[x][0] = 0;
        Q.push(data(x, 0));
    }
    while(not Q.empty()) {
        data x = Q.top();
        Q.pop();
        int p = x.node;
        long long dist = x.dist;
        if(vis[p] == true) continue;

        vis[p] = true;
        for(unsigned i = 0; i < g[p].size(); i++) {
            long long cost = c[p][i] + dist;
            int q = g[p][i];

            if(d[q][0] >= cost) {
                d[q][1] = d[q][0];
                d[q][0] = cost;
                Q.push( data(q, d[q][1]) );
            } else if (d[q][1] > cost) {
                d[q][1] = cost;
                Q.push( data(q, cost) );
            }
        }
    }
    return d[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &p, &q, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 259 ms 248340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 259 ms 248340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 259 ms 248340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -