oj.uz

Submission #497246

# Submission time Handle Problem Language Result Execution time Memory
497246 2021-12-22T20:35:35 Z Ozy Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1716 ms 133292 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define des first
#define peso second

lli n,m,a,b,res;
vector<pair<lli,lli> > hijos[MAX+2];
lli visitados[MAX+2];
set<pair<lli,lli> > cola;
set<pair<lli,lli> >::iterator it;
pair<lli,lli> act;
multiset<lli> llegadas[MAX+2];
multiset<lli>::iterator ot;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

    n = N;
    m = M;
    rep(i,0,m-1) {
        a = R[i][0];
        b = R[i][1];
        hijos[a].push_back({b,L[i]});
        hijos[b].push_back({a,L[i]});
    }

    rep(i,0,K-1) {
        a = P[i];
        cola.insert({0,a});
    }

    while (!cola.empty()) {

        it = cola.begin();
        act = (*it);
        cola.erase(it);

        if (visitados[act.second] == 1) continue;
        visitados[act.second] = 1;

        if (act.second == 0) {
            res = act.first;
            break;
        }

        for (auto h : hijos[act.second]) {
            if (visitados[h.des] == 1) continue;

            a = act.first + h.peso;
            llegadas[h.des].insert(a);

            if (llegadas[h.des].size() > 1)  {

                ot = llegadas[h.des].begin();
                ot++;
                a = (*ot);
                if (cola.find({a,h.des}) == cola.end()) cola.insert({a,h.des});

            }

        }

    }

    return res;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7348 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7504 KB Output is correct
5 Correct 6 ms 7504 KB Output is correct
6 Correct 4 ms 7488 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 4 ms 7504 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7348 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7504 KB Output is correct
5 Correct 6 ms 7504 KB Output is correct
6 Correct 4 ms 7488 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 4 ms 7504 KB Output is correct
9 Correct 6 ms 7888 KB Output is correct
10 Correct 4 ms 7364 KB Output is correct
11 Correct 5 ms 7528 KB Output is correct
12 Correct 9 ms 8528 KB Output is correct
13 Correct 8 ms 8100 KB Output is correct
14 Correct 6 ms 7376 KB Output is correct
15 Correct 5 ms 7632 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7348 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7504 KB Output is correct
5 Correct 6 ms 7504 KB Output is correct
6 Correct 4 ms 7488 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 4 ms 7504 KB Output is correct
9 Correct 6 ms 7888 KB Output is correct
10 Correct 4 ms 7364 KB Output is correct
11 Correct 5 ms 7528 KB Output is correct
12 Correct 9 ms 8528 KB Output is correct
13 Correct 8 ms 8100 KB Output is correct
14 Correct 6 ms 7376 KB Output is correct
15 Correct 5 ms 7632 KB Output is correct
16 Correct 1716 ms 133292 KB Output is correct
17 Correct 82 ms 30860 KB Output is correct
18 Correct 108 ms 28608 KB Output is correct
19 Correct 1387 ms 129108 KB Output is correct
20 Correct 273 ms 72660 KB Output is correct
21 Correct 54 ms 18440 KB Output is correct
22 Correct 538 ms 110916 KB Output is correct