Submission #988769

#	Time	Username	Problem	Language	Result	Execution time	Memory
988769		Whisper	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	238 ms	64544 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = ( n ) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//void setupIO(){
//    #define name "Whisper"
//    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//    //Phu Trong from Nguyen Tat Thanh High School for gifted student
//    srand(time(NULL));
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);
//    cout << fixed << setprecision(10);
//}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define MAX_NODE    100005
#define MAX_EDGE    1000005

int numNode, numEdge;
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v): u(_u), v(_v){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

    int other(int x){return (x ^ u ^ v); }
} edge[MAX_EDGE];

vector<int> G[MAX_NODE];
pair<int, int> F[MAX_NODE];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    numNode = N, numEdge = M;
    for (int i = 0; i < numEdge; ++i){
        edge[i].u = R[i][0], edge[i].v = R[i][1], edge[i].w = L[i];
        G[edge[i].u].emplace_back(i);
        G[edge[i].v].emplace_back(i);
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < numNode; ++i) F[i] = make_pair(INF, INF);

    for (int i = 0; i < K; ++i){
        F[P[i]].first = F[P[i]].second = 0;

        q.emplace(0, P[i]);
    }
    while (q.size()){
        int du, u; tie(du, u) = q.top(); q.pop();
        if (u == 0) return du;
        if (du > F[u].second) continue;
        for (int &i : G[u]){
            int v = edge[i].other(u);
            int current = F[v].second;
            if (F[v].second > du + edge[i].w){
                F[v].second = du + edge[i].w;
                if (F[v].second < F[v].first) swap(F[v].second, F[v].first);
            }
            if (F[v].second < current) q.emplace(F[v].second, v);
        }
    }
    assert(false);
    return 0;
}
//void Whisper(){
//    int R[4][2] = {{0, 1}, {0, 2}, {3, 2}, {2, 4}};
//    int L[4] = {2, 3, 1, 4};
//    int P[3] = {1, 3, 4};
//
//    cout << travel_plan(5, 4, R, L, 3, P);
//}
//
//
//signed main(){
//    setupIO();
//    int Test = 1;
////    cin >> Test;
//    for ( int i = 1 ; i <= Test ; i++ ){
//        Whisper();
//        if (i < Test) cout << '\n';
//    }
//}

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