oj.uz

Submission #479730

# Submission time Handle Problem Language Result Execution time Memory
479730 2021-10-13T01:58:46 Z Yuisuyuno Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 629 ms 48952 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
//#include "crocodile.h"
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

vector<ii> g[100005];
bool is[100005];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0; i<M; i++){
        int u = R[i][0];
        int v = R[i][1];
        int z = L[i];
        g[u].push_back(ii(v,z));
        g[v].push_back(ii(u,z));
    }
    vector<vector<int>> d(N+1,vector<int>(3,inf));
    priority_queue<ii, vii, greater<ii>> q;
    vector<bool> vst(N+1,false);
    for(int i=0; i<K; i++) q.push(ii(0,P[i])), d[P[i]][0]=0;
    while (q.size()){
        int u = q.top().se;
        int du = q.top().fi;
        q.pop();
        if (vst[u]) continue;
        vst[u] = 1;
        for(auto i : g[u]){
            int v = i.fi;
            int uv = du + i.se;
            if (vst[v]) continue;
            bool ok = false;
            if (d[v][1] > uv){
                d[v][1] = uv;
                ok = true;
            }
            sort(all(d[v]));
            if (ok) q.push(ii(d[v][1],v));
        }
    }
    return d[0][1];
}

Compilation message

crocodile.cpp:23:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
   23 | const int inf = 1e10;
      |                 ^~~~
crocodile.cpp:24:18: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+10' to '-2147483648' [-Woverflow]
   24 | const int minf = -1e10;
      |                  ^~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3020 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 476 ms 42936 KB Output is correct
17 Correct 106 ms 16316 KB Output is correct
18 Correct 130 ms 17256 KB Output is correct
19 Correct 629 ms 48952 KB Output is correct
20 Correct 332 ms 36592 KB Output is correct
21 Correct 46 ms 8040 KB Output is correct
22 Correct 330 ms 33580 KB Output is correct