Submission #567610

#	Time	Username	Problem	Language	Result	Execution time	Memory
567610		losmi247	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2062 ms	2644 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+45;

int n,m,k;
vector <pair<int,ll>> g[N];
bool ex[N];

ll dp1[N];
void dfstr(int x,int par){
    vector <ll> svi;
    for(auto f : g[x]){
        int u = f.first;
        if(u == par) continue;
        ll w = f.second;
        dfstr(u,x);
        svi.push_back(dp1[u]+w);
    }

    if(svi.empty()) return;
    assert(svi.size() >= 2);

    sort(svi.begin(),svi.end());
    dp1[x] = svi[1];
}

int zadrvo(){
    dfstr(1,0);
    return dp1[1];
}

ll d1[N],d2[N];
int travel_plan(int br,int M,int R[][2],int L[],int K,int P[]){
    n = br;
    m = M;
    k = K;
    for(int i = 0; i < m; i++){
        g[R[i][0]+1].push_back({R[i][1]+1,L[i]});
        g[R[i][1]+1].push_back({R[i][0]+1,L[i]});
    }
    for(int i = 0; i < k; i++){
        ex[P[i]+1] = 1;
    }

    //return zadrvo();

    for(int i = 1; i <= n; i++) d1[i] = d2[i] = 1e18;
    priority_queue <pair<pair<ll,ll>,int>> pq;
    for(int i = 1; i <= n; i++){
        if(ex[i]){
            pq.push({{0,0},i});
            d1[i] = d2[i] = 0;
        }
    }
    while(!pq.empty()){
        ll drugi = -pq.top().first.first;
        ll prvi = -pq.top().first.second;
        int u = pq.top().second;
        if(d1[u] != prvi || d2[u] != drugi) continue;
        pq.pop();
        for(auto f : g[u]){
            int v = f.first,cost = f.second;
            if(drugi+cost <= d1[v]){
                d2[v] = d1[v];
                d1[v] = drugi+cost;
                if(d1[v] != 1e18 && d2[v] != 1e18) pq.push({{-d2[v],-d1[v]},v});
            }
            else if(drugi+cost <= d2[v]){
                d2[v] = drugi+cost;
                if(d1[v] != 1e18 && d2[v] != 1e18) pq.push({{-d2[v],-d1[v]},v});
            }
        }
    }

    return d2[1];
}

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