제출 #866727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866727		smirichto	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	997 ms	135720 KiB

crocodile

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}


const int N = 1e5+5 ;
int n , m , vis[N] ;
vector<pi> adj[N] ;
multiset<int> neigh[N] ;
int solve() {

    priority_queue<array<int,2> , vector<array<int,2>> , greater<>> pq ;
    vector<int> dist(n , 2e9) ;
    for(int i = 0 ; i<n ; i++){
        for(auto p : adj[i]){
            if(vis[p.F]) neigh[i].insert(p.S) ;
        }
        if(neigh[i].size()>1){
            int val = *next(neigh[i].begin()) ;
            pq.push({val , i}) ;
            dist[i] = val ;
        }
    }
    while(!pq.empty()){
        auto vec = pq.top() ; pq.pop() ;
        int node = vec[1] , d = vec[0] ;
        if(d!=dist[node] || vis[node]) continue;
        vis[node] = 1 ;
        for(auto p : adj[node]){
            int to = p.F , w = p.S ;
            if(vis[to]) continue;
            neigh[to].insert(d + w) ;
            if(neigh[to].size()>1){
                int val = *next(neigh[to].begin()) ;
                if(ckmin(dist[to] , val)) pq.push({val , to}) ;
            }
        }
    }
    return dist[0] ;
}

ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N ;
    m = M ;
    for(int i = 0 ; i<m ; i++){
        int u = R[i][0] , v = R[i][1] , w = L[i] ;
        adj[u].pb({v , w}) ;
        adj[v].pb({u , w}) ;
    }
    for(int i = 0 ; i<K ; i++){
        vis[P[i]] = 1 ;
    }
    return solve() ;
}

//int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
//    io();
//    ll tt = 1;
//    //cin>>tt ;
//    while (tt--) {
//        solve();
//    }
//
//    return 0;
//}

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