oj.uz

Submission #1095691

# Submission time Handle Problem Language Result Execution time Memory
1095691 2024-10-03T01:29:31 Z MtSaka Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 438 ms 62560 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 329 ms 55336 KB Output is correct
17 Correct 58 ms 14928 KB Output is correct
18 Correct 66 ms 16360 KB Output is correct
19 Correct 438 ms 62560 KB Output is correct
20 Correct 173 ms 46932 KB Output is correct
21 Correct 27 ms 6492 KB Output is correct
22 Correct 209 ms 44788 KB Output is correct