Submission #805534

#	Time	Username	Problem	Language	Result	Execution time	Memory
805534		QwertyPi	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	702 ms	67636 KiB

crocodile

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

using namespace std;
const int MAXN = 1e5 + 11;

struct Best2{
    int a = 1 << 30, b = (1 << 30);
    int qry(){
        return b;
    }
    void upd(int x){
        if(x <= a) b = a, a = x;
        else if(x <= b) b = x;
    }
} best[MAXN];

int t[MAXN];
vector<pair<int, int>> G[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void extend(int v){
    for(auto [u, w] : G[v]){
        best[u].upd(t[v] + w);
        pq.push({best[u].qry(), u});
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    fill(t, t + N, 1 << 30);
    for(int i = 0; i < M; i++){
        G[R[i][0]].push_back({R[i][1], L[i]});
        G[R[i][1]].push_back({R[i][0], L[i]});
    }
    for(int i = 0; i < K; i++){
        int v = P[i]; t[v] = 0; extend(v); 
    }

    while(!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if(best[v].qry() != d || t[v] != (1 << 30)) continue;
        t[v] = best[v].qry(); extend(v);
    }
    return t[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void extend(int)':
crocodile.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [u, w] : G[v]){
      |              ^
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [d, v] = pq.top(); pq.pop();
      |              ^

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