oj.uz

Submission #974810

# Submission time Handle Problem Language Result Execution time Memory
974810 2024-05-03T20:16:44 Z aaaaaarroz Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 655 ms 81412 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
 
vector<pair<int,int>> adj[100000];
int visited[100000]={0};
 
int dp[100000]={0};
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for(int i=0;i<K;i++)visited[P[i]]=2;
 
    priority_queue<pair<int,int>> pq;
 
    for(int i=0;i<M;i++){
        int v=R[i][0],w=R[i][1];
        if(!(visited[v]==2&&visited[w]==2)){
            if(!(visited[v]==2))swap(v,w);
            if(visited[v])pq.push({-L[i],w});
        }
        adj[R[i][0]].push_back({R[i][1],L[i]});
        adj[R[i][1]].push_back({R[i][0],L[i]});
    }
 
    while(!pq.empty()){
        int d = -pq.top().first, v = pq.top().second;
        // cout << "s" << v << ' ' << d << '\n';
        pq.pop();
 
        if(visited[v]==2)continue;
        else if(visited[v]==1){
            visited[v]=2;
            dp[v]=d;
            for(pair<int,int> _ : adj[v]){
                int w=_.first, t=_.second;
                pq.push({-(t+d),w});
                // cout << "a" << w << ' ' << -(t+d) << '\n';
            }
        }else{
            visited[v]=1;
        }
    }
 
 
    // cout << pq.top().first;
 
    // for(int i=0;i<n;i++)cout << dp[i] << ' ';
    // cout << '\n';
 
    return dp[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6596 KB Output is correct
4 Correct 2 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6932 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 6 ms 7260 KB Output is correct
13 Correct 5 ms 7260 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6596 KB Output is correct
4 Correct 2 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6932 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 6 ms 7260 KB Output is correct
13 Correct 5 ms 7260 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 613 ms 77196 KB Output is correct
17 Correct 62 ms 16724 KB Output is correct
18 Correct 87 ms 18004 KB Output is correct
19 Correct 655 ms 81412 KB Output is correct
20 Correct 456 ms 70160 KB Output is correct
21 Correct 34 ms 10332 KB Output is correct
22 Correct 437 ms 52268 KB Output is correct