oj.uz

Submission #565559

# Submission time Handle Problem Language Result Execution time Memory
565559 2022-05-21T06:07:23 Z qwerasdfzxcl Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 610 ms 66460 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Vertex{
    int i, d;
    Vertex(){}
    Vertex(int _i, int _d): i(_i), d(_d) {}
    bool operator<(const Vertex &V) const{
        return d > V.d;
    }
};
vector<pair<int, int>> adj[100100];
vector<int> val[100100];
bool visited[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i=0;i<M;i++){
        adj[R[i][0]].emplace_back(R[i][1], L[i]);
        adj[R[i][1]].emplace_back(R[i][0], L[i]);
    }

    priority_queue<Vertex> pq;
    for (int i=0;i<K;i++){
        pq.emplace(P[i], 0);
    }
    while(!pq.empty()){
        auto s = pq.top(); pq.pop();
        //printf(" %d %d\n", s.i, s.d);
        if (!s.i) return s.d;
        if (visited[s.i]) continue;
        visited[s.i] = 1;

        for (auto &v:adj[s.i]) if (!visited[v.first]){
            val[v.first].push_back(v.second + s.d);
            sort(val[v.first].begin(), val[v.first].end());

            if (val[v.first].size()>2) val[v.first].pop_back();
            if (val[v.first].size()==2) pq.emplace(v.first, val[v.first][1]);
        }
    }
    exit(1);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5028 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5028 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 7 ms 5536 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5064 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5028 KB Output is correct
8 Correct 3 ms 5024 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 7 ms 5536 KB Output is correct
13 Correct 6 ms 5460 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5064 KB Output is correct
16 Correct 541 ms 66460 KB Output is correct
17 Correct 78 ms 18448 KB Output is correct
18 Correct 92 ms 18176 KB Output is correct
19 Correct 610 ms 65120 KB Output is correct
20 Correct 268 ms 51884 KB Output is correct
21 Correct 42 ms 10736 KB Output is correct
22 Correct 374 ms 48932 KB Output is correct