oj.uz

Submission #492330

# Submission time Handle Problem Language Result Execution time Memory
492330 2021-12-06T16:03:36 Z ponytail Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 66964 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 69 ms 460 KB Output is correct
5 Correct 71 ms 460 KB Output is correct
6 Correct 34 ms 332 KB Output is correct
7 Correct 93 ms 332 KB Output is correct
8 Correct 83 ms 472 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 69 ms 460 KB Output is correct
5 Correct 71 ms 460 KB Output is correct
6 Correct 34 ms 332 KB Output is correct
7 Correct 93 ms 332 KB Output is correct
8 Correct 83 ms 472 KB Output is correct
9 Correct 50 ms 688 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 21 ms 464 KB Output is correct
12 Correct 125 ms 920 KB Output is correct
13 Correct 47 ms 972 KB Output is correct
14 Correct 9 ms 368 KB Output is correct
15 Correct 18 ms 460 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 69 ms 460 KB Output is correct
5 Correct 71 ms 460 KB Output is correct
6 Correct 34 ms 332 KB Output is correct
7 Correct 93 ms 332 KB Output is correct
8 Correct 83 ms 472 KB Output is correct
9 Correct 50 ms 688 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 21 ms 464 KB Output is correct
12 Correct 125 ms 920 KB Output is correct
13 Correct 47 ms 972 KB Output is correct
14 Correct 9 ms 368 KB Output is correct
15 Correct 18 ms 460 KB Output is correct
16 Execution timed out 2080 ms 66964 KB Time limit exceeded
17 Halted 0 ms 0 KB -