oj.uz

Submission #540216

# Submission time Handle Problem Language Result Execution time Memory
540216 2022-03-19T16:43:49 Z status_coding Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1546 ms 130200 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

bool open[100005];
long long dp[100005];

vector<pair<long long, long long>> v[100005];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0;i<n;i++)
    {
        dp[i]=-1;
        open[i]=false;
    }

    for(int i=0;i<m;i++)
    {
        v[ r[i][0] ].push_back({r[i][1], l[i]});
        v[ r[i][1] ].push_back({r[i][0], l[i]});
    }

    multiset<pair<long long, int>> s;

    for(int i=0;i<k;i++)
    {
        open[ p[i] ] = true;
        s.insert({0, p[i]});
    }

    while(!s.empty())
    {
        int x = s.begin()->second;
        long long len = s.begin()->first;
        s.erase(s.begin());

        if(!open[x])
        {
            open[x]=true;
            continue;
        }

        if(dp[x] != -1)
            continue;

        dp[x]=len;

        for(auto it : v[x])
        {
            if(dp[it.first] == -1)
                s.insert({len + it.second, it.first});
        }
    }

    return dp[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2780 KB Output is correct
2 Correct 2 ms 2616 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2780 KB Output is correct
2 Correct 2 ms 2616 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2856 KB Output is correct
12 Correct 7 ms 3836 KB Output is correct
13 Correct 6 ms 4004 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 3 ms 2780 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2780 KB Output is correct
2 Correct 2 ms 2616 KB Output is correct
3 Correct 2 ms 2660 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2856 KB Output is correct
12 Correct 7 ms 3836 KB Output is correct
13 Correct 6 ms 4004 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 3 ms 2780 KB Output is correct
16 Correct 1534 ms 129600 KB Output is correct
17 Correct 75 ms 16960 KB Output is correct
18 Correct 119 ms 19524 KB Output is correct
19 Correct 1546 ms 124684 KB Output is correct
20 Correct 487 ms 130200 KB Output is correct
21 Correct 43 ms 9504 KB Output is correct
22 Correct 503 ms 65320 KB Output is correct