oj.uz

Submission #958817

# Submission time Handle Problem Language Result Execution time Memory
958817 2024-04-06T19:11:18 Z dpsaveslives Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 348 ms 51172 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 1e5+10;
vector<pair<int,int>> adj[MAXN];
int travel_plan(int N,int M,int (*R)[2],int *L,int K,int *P){
    for(int i = 0;i<M;++i){
        int u = R[i][0], v = R[i][1], w = L[i];
        adj[u].push_back({v,w}); adj[v].push_back({u,w});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    vector<vector<int>> dist(N);
    for(int i = 0;i<K;++i){
        pq.push({0,P[i]});
        dist[P[i]].push_back(0); dist[P[i]].push_back(0);
    }
    while(!pq.empty()){
        int cd = pq.top().f, u = pq.top().s; pq.pop();
      	if(cd != dist[u][1]) continue; 
        if(u == 0) return dist[u][1]; 
        for(auto p : adj[u]){
            int v = p.f, w = p.s;
            if(dist[v].size() == 0){
                dist[v].push_back(dist[u][1]+w);
            }
            else if(dist[v].size() == 1){
                dist[v].push_back(dist[u][1]+w);
                if(dist[v][0] > dist[v][1]) swap(dist[v][0],dist[v][1]); 
                pq.push({dist[v][1],v});
            }
            else{
                if(dist[u][1]+w < dist[v][0]){
                    dist[v][1] = dist[v][0];
                    dist[v][0] = dist[u][1]+w;
                    pq.push({dist[v][1],v});
                }
                else if(dist[u][1]+w < dist[v][1]){
                    dist[v][1] = dist[u][1]+w;
                    pq.push({dist[v][1],v});
                }
            }
        }
    }
    return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6768 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6768 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6768 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6768 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 6 ms 7004 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6768 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6768 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 6 ms 7004 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 300 ms 46284 KB Output is correct
17 Correct 59 ms 16724 KB Output is correct
18 Correct 78 ms 18256 KB Output is correct
19 Correct 348 ms 51172 KB Output is correct
20 Correct 214 ms 41312 KB Output is correct
21 Correct 29 ms 10560 KB Output is correct
22 Incorrect 231 ms 34900 KB Output isn't correct
23 Halted 0 ms 0 KB -