oj.uz

Submission #567615

# Submission time Handle Problem Language Result Execution time Memory
567615 2022-05-23T20:02:55 Z losmi247 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 586 ms 91400 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4236 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 3 ms 4308 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4252 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4236 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 3 ms 4308 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4252 KB Output is correct
9 Correct 4 ms 4692 KB Output is correct
10 Correct 3 ms 4236 KB Output is correct
11 Correct 3 ms 4372 KB Output is correct
12 Correct 6 ms 5008 KB Output is correct
13 Correct 6 ms 5012 KB Output is correct
14 Correct 3 ms 4268 KB Output is correct
15 Correct 4 ms 4308 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4236 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 3 ms 4308 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4252 KB Output is correct
9 Correct 4 ms 4692 KB Output is correct
10 Correct 3 ms 4236 KB Output is correct
11 Correct 3 ms 4372 KB Output is correct
12 Correct 6 ms 5008 KB Output is correct
13 Correct 6 ms 5012 KB Output is correct
14 Correct 3 ms 4268 KB Output is correct
15 Correct 4 ms 4308 KB Output is correct
16 Correct 438 ms 84832 KB Output is correct
17 Correct 77 ms 17684 KB Output is correct
18 Correct 100 ms 20044 KB Output is correct
19 Correct 586 ms 91400 KB Output is correct
20 Correct 280 ms 69580 KB Output is correct
21 Correct 38 ms 10836 KB Output is correct
22 Correct 308 ms 65400 KB Output is correct