oj.uz

Submission #221446

# Submission time Handle Problem Language Result Execution time Memory
221446 2020-04-10T07:27:32 Z emil_physmath Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 175112 KB 
#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long llong;
const llong inf = 1000000000000000LL;
struct Jump
{
    operator int&()
    {
        return to;
    }

    int to;
    llong len;
};

vector<Jump> jumps[100000];
multiset<llong> s[100000];

inline llong D(const multiset<llong>& s)
{
    if (s.empty()) return inf;
    if (s.size() >= 2) return *next(s.begin());
    if (*s.begin()) return inf;
    return 0;
}
int travel_plan(int n, int m, int edges[][2], int l[], int k, int p[])
{
    for (int i = 0; i < m; ++i)
    {
        int u = edges[i][0], v = edges[i][1], w = l[i];
        jumps[u].push_back({v, w});
        jumps[v].push_back({u, w});
    }
    vector<llong> d(n, inf), prevd(n, inf);
    priority_queue<pair<int, int> > q;
    for (int i = 0; i < k; ++i)
    {
        prevd[p[i]] = d[p[i]] = 0;
        q.push({0, p[i]});
    }
    for (int v = 0; v < n; ++v)
        for (Jump to: jumps[v])
            s[v].insert(d[to] + to.len);
    while (!q.empty())
    {
        int v = q.top().second;
        if (d[v] != -q.top().first)
        {
            q.pop();
            continue;
        }
        q.pop();
        // cerr << v << ": " << d[v] << '\n';
        for (Jump to: jumps[v])
        {
            s[to].erase(s[to].find(prevd[v] + to.len));
            s[to].insert(d[v] + to.len);
            if (D(s[to]) < d[to])
            {
                // swap(d[to], prevd[to]);
                d[to] = D(s[to]);
                q.push({-d[to], to});
            }
        }
    }
    return d[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 11 ms 7680 KB Output is correct
12 Correct 21 ms 8960 KB Output is correct
13 Correct 18 ms 9088 KB Output is correct
14 Correct 9 ms 7424 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 10 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 14 ms 8192 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 11 ms 7680 KB Output is correct
12 Correct 21 ms 8960 KB Output is correct
13 Correct 18 ms 9088 KB Output is correct
14 Correct 9 ms 7424 KB Output is correct
15 Correct 10 ms 7680 KB Output is correct
16 Execution timed out 2081 ms 175112 KB Time limit exceeded
17 Halted 0 ms 0 KB -