oj.uz

답안 #221447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221447 2020-04-10T07:29:03 Z emil_physmath 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 2000 ms 159196 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 10 ms 7552 KB Output is correct
5 Correct 10 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 10 ms 7552 KB Output is correct
5 Correct 10 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 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 8 ms 7424 KB Output is correct
11 Correct 11 ms 7680 KB Output is correct
12 Correct 22 ms 8832 KB Output is correct
13 Correct 18 ms 8960 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 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 10 ms 7552 KB Output is correct
5 Correct 10 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 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 8 ms 7424 KB Output is correct
11 Correct 11 ms 7680 KB Output is correct
12 Correct 22 ms 8832 KB Output is correct
13 Correct 18 ms 8960 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 2080 ms 159196 KB Time limit exceeded
17 Halted 0 ms 0 KB -