Submission #713447

#	Time	Username	Problem	Language	Result	Execution time	Memory
713447		That_Salamander	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	725 ms	101536 KiB

crocodile

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,up) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)
#define int long long

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

vector<vector<pii>> conn;
vi a, b;
vector<bool> v;

signed travel_plan(signed n, signed m, signed R[][2], signed L[], signed k, signed P[]) {
    conn.resize(n);
    a.resize(n, 1000000000000ll);
    b.resize(n, 1000000000000ll);
    v.resize(n);

    for (int i = 0; i < m; i++) {
        int t, f, w;
        t = R[i][0];
        f = R[i][1];
        w = L[i];
        conn[t].push_back({f, w});
        conn[f].push_back({t, w});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    for (int i = 0; i < k; i++) {
        int x;
        x = P[i];

        q.push({0, x});
    }

    while (!q.empty()) {
        auto p = q.top(); q.pop();
        int cost = p.first;
        int room = p.second;

        if (room == 0) {
            return cost;
        }

        if (v[room]) continue;
        v[room] = true;

        for (auto c: conn[room]) {
            int to = c.first;
            int time = cost + c.second;

            if (a[to] > time) {
                b[to] = a[to];
                a[to] = time;
            } else if (b[to] > time) {
                b[to] = time;
            }

            q.push({b[to], to});
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:41:85: warning: control reaches end of non-void function [-Wreturn-type]
   41 |     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
      |                                                                                     ^

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11