oj.uz

Submission #799741

# Submission time Handle Problem Language Result Execution time Memory
799741 2023-07-31T22:50:31 Z Liudas Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 5 ms 1236 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<int> c(N);
    for(int i = 0; i < M; i++){
        c[R[i][0]]++;
        c[R[i][1]]++;
    }
    //cout << "???" << endl;
    for(int i = 0; i < K; i ++){
        c[P[i]] += 1e9;
    }
    //cout << "??" << endl;
    vector<pair<int, int>> tree[N];
    for(int i = 0; i < M; i ++){
        if((c[R[i][0]] == 2 || c[R[i][1]] == 2) && R[i][1] && R[i][0]) continue;
        tree[R[i][0]].push_back({R[i][1], L[i]});
        tree[R[i][1]].push_back({R[i][0], L[i]});
    }
   // cout << "???" << endl;
    priority_queue<pair<int, int>> que;
    for(int i = 0; i < K; i++){
        for(auto [l ,r] : tree[P[i]])
            que.push({-r, l});
    }
    vector<int> dist(N, 1e9), cc(N);
    while(!que.empty()){
        int a = -que.top().first, b = que.top().second;
        //cout << b << " " << a << endl;
        que.pop();
        if(cc[b] != 1){
            cc[b]++;
            continue;
        }
        cc[b]++;
        dist[b] = a;
        for(auto [l, r] : tree[b]){
            que.push({-r-a, l});
        }
    }
    return dist[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -