제출 #1095691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095691		MtSaka	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	438 ms	62560 KiB

crocodile

#include "crocodile.h"
#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    vector<int>deg(n);
    vector<vector<pair<int,int>>>g(n);
    rep(i,m){
        g[r[i][0]].eb(r[i][1],l[i]);
        g[r[i][1]].eb(r[i][0],l[i]);
    }
    vector<ll>dist1(n,1e10),dist2(n,1e10);
    rep(i,k)dist1[p[i]]=dist2[p[i]]=0;
    set<pair<ll,int>>st;
    rep(i,k){
        st.emplace(0,p[i]);
    }
    while(!st.empty()){
        auto [d,v]=*st.begin();
        st.erase(st.begin());
        if(dist2[v]!=d)continue;
        for(auto [u,l]:g[v]){
            const ll nxt=d+l;
            if(dist1[u]>nxt){
                ll bef=dist2[u];
                dist2[u]=dist1[u];
                dist1[u]=nxt;
                if(bef!=1e10){
                    st.erase({bef,u});
                    st.emplace(dist2[u],u);
                }
                else if(dist2[u]!=1e10){
                    st.emplace(dist2[u],u);
                }
            }
            else if(dist2[u]>nxt){
                ll bef=dist2[u];
                dist2[u]=nxt;
                if(bef!=1e10){
                    st.erase({bef,u});
                    st.emplace(nxt,u);
                }
                else{
                    st.emplace(nxt,u);
                }
            }
        }
    }
    return dist2[0];
}

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