oj.uz

Submission #893882

# Submission time Handle Problem Language Result Execution time Memory
893882 2023-12-27T16:07:56 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 27876 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 61);

int n, m, k, q;

int startCities[maxn];

vector<pair<int, int>> g[maxn];

long long dist[maxn];

long long ans[maxn];

long long solve(int from, int to)
{
    for (int i = 1; i <= n; ++i)
    {
        ans[i] = -inf;
    }

    priority_queue<pair<long long, int>> pq;
    pq.push(make_pair(dist[from], from));

    ans[from] = dist[from];

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = pq.top().first;
        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = min(curr, dist[g[node][i].first]);

            if (ans[g[node][i].first] < path)
            {
                ans[g[node][i].first] = path;
                pq.push(make_pair(path, g[node][i].first));
            }
        }
    }

    return ans[to];
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    cin >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> startCities[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;

    for (int i = 1; i <= k; ++i)
    {
        pq.push(make_pair(0, startCities[i]));
        dist[startCities[i]] = 0;
    }

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = -pq.top().first;
        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = g[node][i].second + curr;
            int to = g[node][i].first;

            if (dist[to] > path)
            {
                dist[to] = path;
                pq.push(make_pair(-path, to));
            }
        }
    }

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int from, to;
        cin >> from >> to;
        cout << solve(from, to) << "\n";
    }

    return 0;
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message

plan.cpp: In function 'long long int solve(int, int)':
plan.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 87 ms 4664 KB Output is correct
3 Correct 86 ms 4600 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 89 ms 4444 KB Output is correct
6 Correct 93 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 36 ms 4440 KB Output is correct
10 Correct 27 ms 4440 KB Output is correct
11 Correct 43 ms 4444 KB Output is correct
12 Correct 86 ms 4696 KB Output is correct
13 Correct 46 ms 4444 KB Output is correct
14 Correct 28 ms 4440 KB Output is correct
15 Correct 33 ms 4444 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 87 ms 4664 KB Output is correct
3 Correct 86 ms 4600 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 89 ms 4444 KB Output is correct
6 Correct 93 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 36 ms 4440 KB Output is correct
10 Correct 27 ms 4440 KB Output is correct
11 Correct 43 ms 4444 KB Output is correct
12 Correct 86 ms 4696 KB Output is correct
13 Correct 46 ms 4444 KB Output is correct
14 Correct 28 ms 4440 KB Output is correct
15 Correct 33 ms 4444 KB Output is correct
16 Execution timed out 4034 ms 10864 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4568 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 14660 KB Output is correct
2 Correct 255 ms 26796 KB Output is correct
3 Correct 258 ms 27040 KB Output is correct
4 Correct 30 ms 8700 KB Output is correct
5 Correct 254 ms 26808 KB Output is correct
6 Correct 247 ms 26820 KB Output is correct
7 Correct 225 ms 26880 KB Output is correct
8 Correct 281 ms 26848 KB Output is correct
9 Correct 277 ms 26716 KB Output is correct
10 Correct 244 ms 26824 KB Output is correct
11 Correct 263 ms 26624 KB Output is correct
12 Correct 226 ms 26820 KB Output is correct
13 Correct 225 ms 26780 KB Output is correct
14 Correct 254 ms 26816 KB Output is correct
15 Correct 251 ms 27876 KB Output is correct
16 Correct 229 ms 26888 KB Output is correct
17 Correct 258 ms 26768 KB Output is correct
18 Correct 242 ms 26816 KB Output is correct
19 Correct 31 ms 8784 KB Output is correct
20 Correct 298 ms 26824 KB Output is correct
21 Correct 198 ms 26336 KB Output is correct
22 Correct 54 ms 14148 KB Output is correct
23 Correct 47 ms 9296 KB Output is correct
24 Correct 64 ms 14148 KB Output is correct
25 Correct 55 ms 14144 KB Output is correct
26 Correct 52 ms 9600 KB Output is correct
27 Correct 29 ms 8784 KB Output is correct
28 Correct 55 ms 14144 KB Output is correct
29 Correct 30 ms 8796 KB Output is correct
30 Correct 54 ms 14220 KB Output is correct
31 Correct 29 ms 8784 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 87 ms 4664 KB Output is correct
3 Correct 86 ms 4600 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 89 ms 4444 KB Output is correct
6 Correct 93 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 36 ms 4440 KB Output is correct
10 Correct 27 ms 4440 KB Output is correct
11 Correct 43 ms 4444 KB Output is correct
12 Correct 86 ms 4696 KB Output is correct
13 Correct 46 ms 4444 KB Output is correct
14 Correct 28 ms 4440 KB Output is correct
15 Correct 33 ms 4444 KB Output is correct
16 Execution timed out 4034 ms 10864 KB Time limit exceeded
17 Halted 0 ms 0 KB -