oj.uz

Submission #349929

# Submission time Handle Problem Language Result Execution time Memory
349929 2021-01-18T17:50:20 Z idk321 Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 853 ms 57928 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];


struct Comp
{

    bool operator() (const array<ll, 2>&ar1, const array<ll, 2>&ar2) const
    {
        return ar1 > ar2;
    }
};

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>>, Comp> 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 4204 KB Output is correct
2 Correct 4 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 3 ms 4332 KB Output is correct
5 Correct 4 ms 4332 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 3 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 4204 KB Output is correct
2 Correct 4 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 3 ms 4332 KB Output is correct
5 Correct 4 ms 4332 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 3 ms 4332 KB Output is correct
8 Correct 3 ms 4332 KB Output is correct
9 Correct 5 ms 4588 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 4 ms 4332 KB Output is correct
12 Correct 8 ms 4844 KB Output is correct
13 Correct 7 ms 4844 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 4204 KB Output is correct
2 Correct 4 ms 4204 KB Output is correct
3 Correct 3 ms 4332 KB Output is correct
4 Correct 3 ms 4332 KB Output is correct
5 Correct 4 ms 4332 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 3 ms 4332 KB Output is correct
8 Correct 3 ms 4332 KB Output is correct
9 Correct 5 ms 4588 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 4 ms 4332 KB Output is correct
12 Correct 8 ms 4844 KB Output is correct
13 Correct 7 ms 4844 KB Output is correct
14 Correct 3 ms 4332 KB Output is correct
15 Correct 4 ms 4332 KB Output is correct
16 Correct 773 ms 57928 KB Output is correct
17 Correct 79 ms 11372 KB Output is correct
18 Correct 101 ms 12652 KB Output is correct
19 Correct 853 ms 51936 KB Output is correct
20 Correct 508 ms 46444 KB Output is correct
21 Correct 43 ms 7672 KB Output is correct
22 Correct 438 ms 33388 KB Output is correct