oj.uz

Submission #1107562

# Submission time Handle Problem Language Result Execution time Memory
1107562 2024-11-01T13:31:44 Z chaoslong Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 360 ms 110880 KB 
// Calm down.
// Think three times, code twice.
#include "bits/stdc++.h"
#include "crocodile.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353
const ll oo = 1e18;

ll d[N][2];
vector<pii> a[N];
priority_queue<pii, vector<pii>, greater<pii>> q;

//int n, m, r[N][2], l[N], k, p[N];
//int n, int m, int r[][2], int l[], int k, int p[]

void dijkstra() {
    while(q.size()) {
        int u = q.top().nd; ll du = q.top().st; q.pop();
        if(du != d[u][1]) continue;
        for(pii e: a[u]) {
            ll v = e.nd, dv = e.st + du;
            if(dv < d[v][0]) {
                if (d[v][0] != d[v][1] && d[v][0] < 1e18){
                  d[v][1] = d[v][0];
                  q.push({d[v][1], v});
                }
                d[v][0] = dv;
            } else if(dv < d[v][1]) {
                d[v][1] = dv;
                q.push({d[v][1], v});
            }
        }
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    forf(i, 0, m) {
        a[r[i][0]].pb({l[i], r[i][1]});
        a[r[i][1]].pb({l[i], r[i][0]});
    }
    memset(d, 63, sizeof d);
    forf(i, 0, k) {
        q.push({0, p[i]});
        d[p[i]][0] = d[p[i]][1] = 0;
    }
    dijkstra();
    return d[0][1];
}

//signed main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//    #ifdef LOCAL
//        freopen("grader.in.7","r",stdin);
//        freopen(file".out","w",stdout);
//    #endif
//    cin >> n >> m >> k;
//    forf(i, 0, m) {
//        cin >> r[i][0] >> r[i][1] >> l[i];
//    }
//    forf(i, 0, k) cin >> p[i];
//    int t = 1;
//    //cin >> t;
//    while(t--) cout << travel_plan();
//}
/*
1.self check:
2.long long
3.size of array
4.code for testing
5.initializing
6.modulo number
*/
/**
  ∧__∧
（｀•ω• )づ__∧
（つ　 /( •ω•。)
  しーＪ (nnノ) pat pat
**/
/**  /\_/\
*   (= ._.)
*   / >☕ \>💻
**/

Compilation message

crocodile.cpp:99:9: warning: "/*" within comment [-Wcomment]
   99 | /**  /\_/\
      |

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43600 KB Output is correct
2 Correct 7 ms 43600 KB Output is correct
3 Correct 7 ms 43600 KB Output is correct
4 Correct 8 ms 43600 KB Output is correct
5 Correct 8 ms 43768 KB Output is correct
6 Correct 9 ms 43768 KB Output is correct
7 Correct 7 ms 43600 KB Output is correct
8 Correct 8 ms 43600 KB Output is correct
9 Correct 8 ms 43856 KB Output is correct
10 Correct 7 ms 43600 KB Output is correct
11 Correct 7 ms 43600 KB Output is correct
12 Correct 9 ms 44112 KB Output is correct
13 Correct 10 ms 44112 KB Output is correct
14 Correct 8 ms 43600 KB Output is correct
15 Correct 8 ms 43600 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43600 KB Output is correct
2 Correct 7 ms 43600 KB Output is correct
3 Correct 7 ms 43600 KB Output is correct
4 Correct 8 ms 43600 KB Output is correct
5 Correct 8 ms 43768 KB Output is correct
6 Correct 9 ms 43768 KB Output is correct
7 Correct 7 ms 43600 KB Output is correct
8 Correct 8 ms 43600 KB Output is correct
9 Correct 8 ms 43856 KB Output is correct
10 Correct 7 ms 43600 KB Output is correct
11 Correct 7 ms 43600 KB Output is correct
12 Correct 9 ms 44112 KB Output is correct
13 Correct 10 ms 44112 KB Output is correct
14 Correct 8 ms 43600 KB Output is correct
15 Correct 8 ms 43600 KB Output is correct
16 Correct 307 ms 104736 KB Output is correct
17 Correct 60 ms 51528 KB Output is correct
18 Correct 76 ms 53660 KB Output is correct
19 Correct 360 ms 110880 KB Output is correct
20 Correct 195 ms 92568 KB Output is correct
21 Correct 32 ms 47860 KB Output is correct
22 Correct 219 ms 88136 KB Output is correct