oj.uz

Submission #842079

# Submission time Handle Problem Language Result Execution time Memory
842079 2023-09-02T11:18:47 Z TS_2392 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 378 ms 76116 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
 
using namespace std;
 
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED        ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL           cout << '\n'
#define dbg(x)       cout << #x << " = " << (x) << ' '
#define dbgp(x)      cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
 
#define epl          emplace
#define pb           push_back
#define eb           emplace_back
#define fi           first
#define se           second
#define mp           make_pair
 
#define sqr(x)       ((x) * (x))
#define all(x)       (x).begin(), (x).end()
#define rall(x)      (x).rbegin(), (x).rend()
#define lwb          lower_bound
#define upb          upper_bound
#define ctz          __builtin_ctzll
#define pct          __builtin_popcountll
 
typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;
 
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
 
int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//-----------------------------------------------------------------------//
const int N = 1e5 + 3, M = 1e6 + 3;
const ll oo = 1e17;
int n, m, k;// R[M][2], L[M], P[N];
vector<pii> adj[N];
pll d[N];
struct state{
    int vertex; pll di;
    bool operator < (const state &oth) const{
        return di.se > oth.di.se;
    }
};
priority_queue<state> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N, m = M, k = K;
    for(int i = 0; i < m; ++i){
        adj[R[i][0]].eb(R[i][1], L[i]);
        adj[R[i][1]].eb(R[i][0], L[i]);
    }
    for(int i = 0; i < n; ++i) d[i] = {oo, oo};
    for(int i = 0; i < k; ++i){
        d[P[i]] = {0, 0};
        pq.push({P[i], d[P[i]]});
    }
    while(!pq.empty()){
        int u = pq.top().vertex;
        pll dist = pq.top().di;
        pq.pop();
        if(dist != d[u]) continue;
        if(d[u].se == oo) break;
        for(int i = 0; i < adj[u].size(); ++i){
            int v = adj[u][i].fi;
            ll w = adj[u][i].se;
            if(d[v].fi > d[u].se + w){
                d[v].se = d[v].fi;
                d[v].fi = d[u].se + w;
                pq.push({v, d[v]});
            }
            else if(minimize(d[v].se, d[u].se + w)){
                pq.push({v, d[v]});
            }
        }
    }
    return d[0].se;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < adj[u].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6656 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 4 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6656 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 4 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 308 ms 68516 KB Output is correct
17 Correct 72 ms 22728 KB Output is correct
18 Correct 82 ms 24520 KB Output is correct
19 Correct 378 ms 76116 KB Output is correct
20 Correct 207 ms 54100 KB Output is correct
21 Correct 39 ms 15440 KB Output is correct
22 Correct 229 ms 52592 KB Output is correct