oj.uz

Submission #492321

# Submission time Handle Problem Language Result Execution time Memory
492321 2021-12-06T15:56:37 Z ponytail Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 83176 KB 
#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]);


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    long long dist[N];
    for(int i=0; i<N; i++) dist[i] = 1e15;
    dist[0] = 0;
    bool vis[N];
    for(int i=0; i<N; i++) vis[i] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > >pq;
    for(int i=0; i<N; i++) pq.push({dist[i], i});
    vector<pair<int, long long> > adj[N];
    for(int i=0; i<M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    while(pq.size()) {
        pair<long long, int> t = pq.top(); pq.pop();
        if(!vis[t.second]) {
            vis[t.second] = 1;
            for(pair<int, long long> x : adj[t.second]) {
                if(!vis[x.first] && dist[t.second] != 1e15 && dist[x.first] > dist[t.second] + x.second) {
                    dist[x.first] = dist[t.second] + x.second;
                    pq.push({dist[x.first], x.first});
                }
            }
        }
    }
    long long dp[N];
    for(int i=0; i<N; i++) dp[i] = 1e15;
    pair<long long, int> p[N];
    for(int i=0; i<N; i++) p[i] = {dist[i], i};
    sort(p, p+N);
    reverse(p, p+N);
    for(int i=0; i<K; i++) {
        dp[P[i]] = 0;
    }
    for(int it=0; it<N; it++) {
        for(int i=0; i<N; i++) {
            vector<long long> v;
            for(pair<int, long long> x : adj[p[i].second]) {
                if(dp[x.first] != 1e15) {
                    v.push_back(dp[x.first] + x.second);
                }
            }
            sort(v.begin(), v.end());
            if(v.size() > 1) dp[p[i].second] = min(dp[p[i].second], v[1]);
        }
    }
    return (int)dp[0];
    
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 81 ms 464 KB Output is correct
5 Correct 67 ms 460 KB Output is correct
6 Correct 37 ms 396 KB Output is correct
7 Correct 71 ms 332 KB Output is correct
8 Correct 92 ms 468 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 81 ms 464 KB Output is correct
5 Correct 67 ms 460 KB Output is correct
6 Correct 37 ms 396 KB Output is correct
7 Correct 71 ms 332 KB Output is correct
8 Correct 92 ms 468 KB Output is correct
9 Correct 53 ms 588 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 24 ms 460 KB Output is correct
12 Correct 135 ms 1044 KB Output is correct
13 Correct 49 ms 1144 KB Output is correct
14 Correct 7 ms 332 KB Output is correct
15 Correct 19 ms 484 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 9 ms 332 KB Output is correct
4 Correct 81 ms 464 KB Output is correct
5 Correct 67 ms 460 KB Output is correct
6 Correct 37 ms 396 KB Output is correct
7 Correct 71 ms 332 KB Output is correct
8 Correct 92 ms 468 KB Output is correct
9 Correct 53 ms 588 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 24 ms 460 KB Output is correct
12 Correct 135 ms 1044 KB Output is correct
13 Correct 49 ms 1144 KB Output is correct
14 Correct 7 ms 332 KB Output is correct
15 Correct 19 ms 484 KB Output is correct
16 Execution timed out 2065 ms 83176 KB Time limit exceeded
17 Halted 0 ms 0 KB -