oj.uz

Submission #1107558

# Submission time Handle Problem Language Result Execution time Memory
1107558 2024-11-01T13:22:23 Z chaoslong Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 321 ms 110780 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]) {
                ll tmp = d[v][0];
                d[v][0] = dv;
                d[v][1] = tmp;
//                cout << u << " " << v << " " << d[v][0] << " " << d[v][1] << " 1\n";
                if(d[v][1] <= 1e9)
                q.push({d[v][1], v});
            } else if(dv < d[v][1]) {
                d[v][1] = dv;
//                cout << u << " " << v << " " << d[v][0] << " " << d[v][1] << " 2\n";
                if(d[v][1] <= 1e9)
                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:102:9: warning: "/*" within comment [-Wcomment]
  102 | /**  /\_/\
      |

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 43656 KB Output is correct
5 Correct 7 ms 43600 KB Output is correct
6 Correct 7 ms 43664 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 43656 KB Output is correct
5 Correct 7 ms 43600 KB Output is correct
6 Correct 7 ms 43664 KB Output is correct
7 Correct 7 ms 43600 KB Output is correct
8 Correct 8 ms 43600 KB Output is correct
9 Correct 9 ms 43856 KB Output is correct
10 Correct 8 ms 43600 KB Output is correct
11 Correct 8 ms 43816 KB Output is correct
12 Correct 9 ms 44128 KB Output is correct
13 Correct 10 ms 44112 KB Output is correct
14 Correct 7 ms 43600 KB Output is correct
15 Correct 7 ms 43600 KB Output is correct

Subtask #3
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 43656 KB Output is correct
5 Correct 7 ms 43600 KB Output is correct
6 Correct 7 ms 43664 KB Output is correct
7 Correct 7 ms 43600 KB Output is correct
8 Correct 8 ms 43600 KB Output is correct
9 Correct 9 ms 43856 KB Output is correct
10 Correct 8 ms 43600 KB Output is correct
11 Correct 8 ms 43816 KB Output is correct
12 Correct 9 ms 44128 KB Output is correct
13 Correct 10 ms 44112 KB Output is correct
14 Correct 7 ms 43600 KB Output is correct
15 Correct 7 ms 43600 KB Output is correct
16 Correct 276 ms 104724 KB Output is correct
17 Correct 56 ms 51364 KB Output is correct
18 Correct 69 ms 53668 KB Output is correct
19 Correct 321 ms 110780 KB Output is correct
20 Correct 187 ms 92576 KB Output is correct
21 Correct 41 ms 47688 KB Output is correct
22 Incorrect 204 ms 87988 KB Output isn't correct
23 Halted 0 ms 0 KB -