oj.uz

Submission #492323

# Submission time Handle Problem Language Result Execution time Memory
492323 2021-12-06T15:57:17 Z ponytail Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 67036 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<100; 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 3 ms 332 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 11 ms 460 KB Output is correct
8 Correct 10 ms 460 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 3 ms 332 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 11 ms 460 KB Output is correct
8 Correct 10 ms 460 KB Output is correct
9 Correct 30 ms 588 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 10 ms 460 KB Output is correct
12 Correct 65 ms 844 KB Output is correct
13 Correct 37 ms 972 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 10 ms 456 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 3 ms 332 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 11 ms 460 KB Output is correct
8 Correct 10 ms 460 KB Output is correct
9 Correct 30 ms 588 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 10 ms 460 KB Output is correct
12 Correct 65 ms 844 KB Output is correct
13 Correct 37 ms 972 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 10 ms 456 KB Output is correct
16 Execution timed out 2087 ms 67036 KB Time limit exceeded
17 Halted 0 ms 0 KB -