Submission #472631

#	Time	Username	Problem	Language	Result	Execution time	Memory
472631		hidden1	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	703 ms	63512 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const int MAX_N = 1e5 + 10;
vector<pair<int, int> > g[MAX_N];
int n, m;
bool starting[MAX_N];
int cnt[MAX_N];
vector<int> dist[MAX_N];

bool push(int x, int val) {
    vector<int> cpy = dist[x];
    dist[x].push_back(val);
    sort(dist[x].begin(), dist[x].end());
    dist[x].resize(2);
    return dist[x] != cpy;
}

int dij() {
    priority_queue<pair<int, int> > pq;
    for(int i = 0; i < n; i ++) {
        dist[i] = {mod, mod};
        if(starting[i]) {
            dist[i] = {0, 0};
            pq.push({0, i});
            pq.push({0, i});
            cnt[i] = 0;
        }
    }
    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        cnt[curr.second] ++;
        if(cnt[curr.second] != 2) {
            continue;
        }
        if(curr.second == 0) {
            return -curr.first;
        }
        for(auto it : g[curr.second]) {
            if(push(it.first, -curr.first  + it.second)) {
                pq.push({curr.first - it.second, it.first});
            }
        }
    }
    return -1;
}

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 a = R[i][0], b = R[i][1], c = L[i];
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 0; i < K; i ++) {
        starting[P[i]] = true;
    }
    return dij();
}

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