Submission #567615

#	Time	Username	Problem	Language	Result	Execution time	Memory
567615		losmi247	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	586 ms	91400 KiB

crocodile

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

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];
}

struct Best{
	ll p1 = inf, p2 = inf;
	Best(){
		p1 = p2 = inf;
	}
	Best(int p1, int p2): p1(p1), p2(p2){}
	bool ok(){
		return p1 != inf and p2 != inf;
	}
	void add(int num){
		if (num <= p1)
			p2 = p1, p1 = num;
		else if (num <= p2)
			p2 = num;
	}
};
bool operator < (Best a, Best b){
	return (a.p2 != b.p2) ? (a.p2 < b.p2) : (a.p1 < b.p1);
}
bool operator > (Best a, Best b){
	return (a.p2 != b.p2) ? (a.p2 > b.p2) : (a.p1 > b.p1);
}
bool operator == (Best a, Best b){
	return a.p1 == b.p1 and a.p2 == b.p2;
}
bool operator != (Best a, Best b){
	return not (a == b);
}

Best f[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();

    priority_queue <pair<Best,int>,vector<pair<Best,int>>,greater<pair<Best,int>>> pq;
    for(int i = 1; i <= n; i++){
        if(ex[i]){
            f[i] = {0,0};
            pq.push({f[i],i});
        }
        else{
            f[i] = Best();
        }
    }
    while(!pq.empty()){
        pair <Best,int> cur = pq.top();
        pq.pop();
        int u = cur.second;
        Best sta = cur.first;
        if(sta != f[u]) continue;
        for(auto ff : g[u]){
            int v = ff.first,cost = ff.second;

            ll novav = sta.p2+cost;
            Best dete = f[v];
            dete.add(novav);

            if(dete < f[v]){
                f[v] = dete;
                if(f[v].ok()) pq.push({f[v],v});
            }
        }
    }

    return f[1].p2;
}

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