oj.uz

Submission #62165

# Submission time Handle Problem Language Result Execution time Memory
62165 2018-07-27T15:59:36 Z reality Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1303 ms 69352 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "crocodile.h"

const int Nmax = (int)(1e6) + 5;

int D[Nmax];
int was[Nmax];

vector < pii > g[Nmax];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n = N;
    int m = M;
    for (int i = 0;i < m;++i)
        g[R[i][0]].pb(mp(R[i][1],L[i])),g[R[i][1]].pb(mp(R[i][0],L[i]));
    priority_queue < pii , vector < pii > , greater < pii > > Q;
    for (int i = 0;i < n + n;++i)
        D[i] = 1e9 + 55;
    for (int i = 0;i < K;++i)
    {
        D[P[i] * 2] = D[P[i] * 2 + 1] = 0;
        Q.push(mp(0,P[i] * 2));
        Q.push(mp(0,P[i] * 2 + 1));
    }
    while (!Q.empty())
    {
        int node = Q.top().se;
        Q.pop();
        ++was[node];
        if (was[node] > 1) continue;
        if ((node & 1) && was[node ^ 1])
        {
            for (auto it : g[node / 2])
            {
                int v = it.fi;
                if (D[v * 2] >= D[node] + it.se)
                    D[v * 2 + 1] = D[v * 2],D[v * 2] = D[node] + it.se,Q.push(mp(D[v * 2],v * 2)),Q.push(mp(D[v * 2 + 1],v * 2 + 1));
                else
                if (D[v * 2 + 1] > D[node] + it.se)
                    D[v * 2 + 1] = D[node] + it.se,Q.push(mp(D[v * 2 + 1],v * 2 + 1));
            }
        }
    }
    return D[1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 25 ms 23912 KB Output is correct
3 Correct 31 ms 23964 KB Output is correct
4 Correct 30 ms 23984 KB Output is correct
5 Correct 29 ms 23996 KB Output is correct
6 Correct 28 ms 24172 KB Output is correct
7 Correct 33 ms 24172 KB Output is correct
8 Correct 27 ms 24172 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 25 ms 23912 KB Output is correct
3 Correct 31 ms 23964 KB Output is correct
4 Correct 30 ms 23984 KB Output is correct
5 Correct 29 ms 23996 KB Output is correct
6 Correct 28 ms 24172 KB Output is correct
7 Correct 33 ms 24172 KB Output is correct
8 Correct 27 ms 24172 KB Output is correct
9 Correct 28 ms 24224 KB Output is correct
10 Correct 33 ms 24224 KB Output is correct
11 Correct 31 ms 24224 KB Output is correct
12 Correct 32 ms 24508 KB Output is correct
13 Correct 39 ms 24528 KB Output is correct
14 Correct 32 ms 24528 KB Output is correct
15 Correct 31 ms 24528 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 25 ms 23912 KB Output is correct
3 Correct 31 ms 23964 KB Output is correct
4 Correct 30 ms 23984 KB Output is correct
5 Correct 29 ms 23996 KB Output is correct
6 Correct 28 ms 24172 KB Output is correct
7 Correct 33 ms 24172 KB Output is correct
8 Correct 27 ms 24172 KB Output is correct
9 Correct 28 ms 24224 KB Output is correct
10 Correct 33 ms 24224 KB Output is correct
11 Correct 31 ms 24224 KB Output is correct
12 Correct 32 ms 24508 KB Output is correct
13 Correct 39 ms 24528 KB Output is correct
14 Correct 32 ms 24528 KB Output is correct
15 Correct 31 ms 24528 KB Output is correct
16 Correct 1045 ms 63804 KB Output is correct
17 Correct 207 ms 63804 KB Output is correct
18 Correct 232 ms 63804 KB Output is correct
19 Correct 1303 ms 69352 KB Output is correct
20 Correct 558 ms 69352 KB Output is correct
21 Correct 97 ms 69352 KB Output is correct
22 Correct 513 ms 69352 KB Output is correct