Submission #1126366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126366		andrewp	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	427 ms	47168 KiB

crocodile

//Dedicated to my love,ivaziva 
#include <bits/stdc++.h> 
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back 
#define me(a, x) memset(a, x, sizeof(a)) 
#define vi vector<int> 
#define i128 __int128
using namespace std;    
const int N = 1e5 + 7; 
int n, m, k;
bool spec[N]; 
vector<pair<int, int>> g[N], sp[N];
array<int, 2> dist[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N, m = M, k = K; 
    L(i, 0, n - 1) {
        dist[i] = {(int)1e9, (int)1e9};
    }
    L(i, 0, m - 1) {
        g[R[i][0]].pb(make_pair(R[i][1], L[i]));
        g[R[i][1]].pb(make_pair(R[i][0], L[i])); 
    } 
    priority_queue<pair<int, int>> Q;
    L(i, 0, k - 1) {
        Q.push(make_pair(0, P[i]));
        dist[P[i]] = {0, 0};
    }   
    while(!Q.empty()) {
        pair<int, int> x = Q.top();
        Q.pop();
        x.first *= -1;
        if(dist[x.second][1] < x.first) continue;
        for(auto u : g[x.second]) {
            if(x.first + u.second < dist[u.first][0]) {
                if(dist[u.first][0] < dist[u.first][1]) {
                    Q.push(make_pair(-dist[u.first][0], u.first));
                }
                dist[u.first][1] = dist[u.first][0];
                dist[u.first][0] = x.first + u.second;
            } else if(x.first + u.second < dist[u.first][1]) {
                dist[u.first][1] = x.first + u.second;
                Q.push(make_pair(-dist[u.first][1], u.first));
            }
        }
    }
    return dist[0][1];
}   
// int main() {
//     ios :: sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);

//     int N = 5, M = 7, K = 2;
//     int R[M][2], L[M], P[K];
//     L(i, 0, M - 1) cin >> R[i][0] >> R[i][1];
//     L(i, 0, M - 1) cin >> L[i];
//     L(i, 0, K - 1) cin >> P[i]; 
//     cout << travel_plan(N, M, R, L, K, P) << '\n';
//     return 0;
// }   

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