oj.uz

Submission #1107555

# Submission time Handle Problem Language Result Execution time Memory
1107555 2024-11-01T13:05:16 Z chaoslong Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 318 ms 94752 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 <int,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;

int 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, du = q.top().st; q.pop();
        if(du > d[u][1]) continue;
        for(pii e: a[u]) {
            int v = e.nd, dv = e.st + du;
            if(dv < d[v][0]) {
                int 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(file".inp","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 6 ms 35408 KB Output is correct
2 Correct 6 ms 35408 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 9 ms 35408 KB Output is correct
5 Correct 6 ms 35588 KB Output is correct
6 Correct 6 ms 35408 KB Output is correct
7 Correct 7 ms 35720 KB Output is correct
8 Correct 6 ms 35420 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35408 KB Output is correct
2 Correct 6 ms 35408 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 9 ms 35408 KB Output is correct
5 Correct 6 ms 35588 KB Output is correct
6 Correct 6 ms 35408 KB Output is correct
7 Correct 7 ms 35720 KB Output is correct
8 Correct 6 ms 35420 KB Output is correct
9 Correct 8 ms 35664 KB Output is correct
10 Correct 7 ms 35408 KB Output is correct
11 Correct 7 ms 35580 KB Output is correct
12 Correct 10 ms 35664 KB Output is correct
13 Correct 9 ms 35920 KB Output is correct
14 Correct 7 ms 35408 KB Output is correct
15 Correct 7 ms 35576 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35408 KB Output is correct
2 Correct 6 ms 35408 KB Output is correct
3 Correct 7 ms 35408 KB Output is correct
4 Correct 9 ms 35408 KB Output is correct
5 Correct 6 ms 35588 KB Output is correct
6 Correct 6 ms 35408 KB Output is correct
7 Correct 7 ms 35720 KB Output is correct
8 Correct 6 ms 35420 KB Output is correct
9 Correct 8 ms 35664 KB Output is correct
10 Correct 7 ms 35408 KB Output is correct
11 Correct 7 ms 35580 KB Output is correct
12 Correct 10 ms 35664 KB Output is correct
13 Correct 9 ms 35920 KB Output is correct
14 Correct 7 ms 35408 KB Output is correct
15 Correct 7 ms 35576 KB Output is correct
16 Correct 273 ms 90304 KB Output is correct
17 Correct 52 ms 45384 KB Output is correct
18 Correct 66 ms 46668 KB Output is correct
19 Correct 318 ms 94752 KB Output is correct
20 Correct 183 ms 82960 KB Output is correct
21 Correct 26 ms 38992 KB Output is correct
22 Incorrect 186 ms 76056 KB Output isn't correct
23 Halted 0 ms 0 KB -