oj.uz

Submission #479726

# Submission time Handle Problem Language Result Execution time Memory
479726 2021-10-13T01:55:33 Z Yuisuyuno Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 596 ms 63036 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,0));
    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;
            int &a = d[v][0];
            int &b = d[v][1];
            int s = b;
            if (!a || a > uv) b = a, a = uv;
            else if  (!b || b > uv) b = uv;
            if (b!=s) q.push(ii(b,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 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2760 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 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 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2760 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 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 6 ms 3140 KB Output is correct
13 Correct 5 ms 3148 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 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 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2760 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 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 6 ms 3140 KB Output is correct
13 Correct 5 ms 3148 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 470 ms 57872 KB Output is correct
17 Correct 80 ms 18372 KB Output is correct
18 Correct 112 ms 19544 KB Output is correct
19 Correct 596 ms 63036 KB Output is correct
20 Correct 355 ms 49592 KB Output is correct
21 Correct 41 ms 9028 KB Output is correct
22 Correct 341 ms 47300 KB Output is correct