oj.uz

Submission #349928

# Submission time Handle Problem Language Result Execution time Memory
349928 2021-01-18T17:47:23 Z idk321 Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 888 ms 73980 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 100001;
const ll M = 2000000000000000000LL;
vector<array<int, 2>> adj[N];
vector<array<ll, 2>> path(N, {M, M});
bool vis[N];


int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    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]});
    }

    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    for (int i = 0; i < k; i++)
    {
        int node = p[i];
        path[node] = {0, 0};
        pq.push({0, node});
    }

    while (!pq.empty())
    {
        int node = pq.top()[1];
        ll dist = pq.top()[0];
        pq.pop();
        if (vis[node]) continue;
        vis[node] = true;
        for (auto next : adj[node])
        {
            if (vis[next[0]]) continue;
            array<ll, 3> ar {path[next[0]][0], path[next[0]][1], dist + next[1]};
            sort(ar.begin(), ar.end());
            path[next[0]][0] = ar[0];
            path[next[0]][1] = ar[1];
            //cout << ar[0] << " " << ar[1] << " " << ar[2] << " "  << next[0] << endl;
            if (path[next[0]][1] != M) pq.push({path[next[0]][1], next[0]});
        }
    }

  return path[0][1];
}

///home/domen/Downloads/crocodile/crocodile.cpp|19|error: request for member ‘push_back’ in ‘(*(r + ((sizetype)(((long unsigned int)i) * 8))))[1]’, which is of non-class type ‘int’|

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 4 ms 4332 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4332 KB Output is correct
8 Correct 3 ms 4332 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 4 ms 4332 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4332 KB Output is correct
8 Correct 3 ms 4332 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 3 ms 4332 KB Output is correct
11 Correct 4 ms 4460 KB Output is correct
12 Correct 8 ms 4972 KB Output is correct
13 Correct 7 ms 4972 KB Output is correct
14 Correct 3 ms 4332 KB Output is correct
15 Correct 4 ms 4332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 4 ms 4332 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4332 KB Output is correct
8 Correct 3 ms 4332 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 3 ms 4332 KB Output is correct
11 Correct 4 ms 4460 KB Output is correct
12 Correct 8 ms 4972 KB Output is correct
13 Correct 7 ms 4972 KB Output is correct
14 Correct 3 ms 4332 KB Output is correct
15 Correct 4 ms 4332 KB Output is correct
16 Correct 819 ms 73980 KB Output is correct
17 Correct 78 ms 14700 KB Output is correct
18 Correct 102 ms 16108 KB Output is correct
19 Correct 888 ms 68320 KB Output is correct
20 Correct 549 ms 59464 KB Output is correct
21 Correct 44 ms 9068 KB Output is correct
22 Correct 444 ms 47596 KB Output is correct