Submission #1280059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280059		zagaro	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	568 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
    ll nod, val, par, r;
    bl B;
    vector<vector<pair<ll,ll> > > adj(n+1);
    vector<pair<ll,ll> > dis(n+1, {LONG_LONG_MAX, LONG_LONG_MAX});
    vector<ll> d(n+1, LONG_LONG_MAX);
    vector<pair<ll,ll> > ubi(n+1);
    vector<bl> ext(n+1, false);
    vector<bl> vis(n+1, false);
    vector<ll> vec(n+1, 0);
    for(int i=0;i<m;i++){
        adj[R[i][0]+1].push_back({R[i][1]+1, L[i]});
        adj[R[i][1]+1].push_back({R[i][0]+1, L[i]});
        vec[R[i][0]+1]++;
        vec[R[i][1]+1]++;
    }
    priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll> >, greater<tuple<ll,ll,ll> > > pq;
    for(int i=0;i<k;i++){
        ext[P[i]+1] = true;
        for(int j=0;j<adj[P[i]+1].size();j++){
            pq.push({adj[P[i]+1][j].second, adj[P[i]+1][j].first, P[i]+1});
        }
        vis[P[i]+1] = true;
    }
    wl(!pq.empty()){
        tie(val, nod, par) = pq.top();
        pq.pop();
        B=false;
        if(val < dis[nod].first){
            dis[nod].second = dis[nod].first;
            dis[nod].first = val;
            ubi[nod].second = ubi[nod].first;
            ubi[nod].first = par;
            B = true;
        }
        else if(val < dis[nod].second){
            dis[nod].second = val;
            ubi[nod].second = par;
            B = true;
        }
        if(B && dis[nod].second != LONG_LONG_MAX){
            vis[nod] = true;
            for(int i=0;i<adj[nod].size();i++){
                if(!vis[adj[nod][i].first]){
                    pq.push({dis[nod].first+adj[nod][i].second, adj[nod][i].first, nod});
                }
            }
        }
    }
    r = 1;
    wl(!ext[r])r = ubi[r].second;
    pq.push({0, 1, 0});
    wl(!pq.empty()){
        tie(val, nod, par) = pq.top();
        pq.pop();
        if(val < d[nod]){
            d[nod] = val;
            for(int i=0;i<adj[nod].size();i++){
                pq.push({val+adj[nod][i].second, adj[nod][i].first, 0});
            }
        }
    }
    return d[r];
}

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