oj.uz

Submission #1039673

# Submission time Handle Problem Language Result Execution time Memory
1039673 2024-07-31T07:25:12 Z _callmelucian Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 289 ms 61736 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
vector<pii> adj[mn];
int vis[mn];

struct helper {
    int best, secBest;

    helper() : best(INT_MAX), secBest(INT_MAX) {}
    helper (int b, int sb) : best(b), secBest(sb) {}

    bool push (int cur) {
        if (cur < best) return secBest = best, best = cur, 1;
        else {
            if (cur >= secBest) return 0;
            return secBest = cur, 1;
        }
    }

    bool operator < (helper o) const {
        if (best == o.best) return secBest > o.secBest;
        return best > o.best;
    }
} dist[mn];

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; i++) {
        adj[r[i][0]].push_back({r[i][1], l[i]});
        adj[r[i][1]].push_back({r[i][0], l[i]});
    }

    priority_queue<pii> pq;
    for (int i = 0; i < k; i++) {
        int u = p[i];
        vis[u] = 1, dist[u] = helper(0, 0);
        pq.push({0, u});
    }

    //for (int i = 1; i <= n; i++) pq.push({dist[i], i});

    while (pq.size()) {
        int u = pq.top().second; pq.pop();
        if (vis[u] == 2) continue;
        if (++vis[u] == 1) continue;

        for (auto [v, w] : adj[u])
            if (dist[v].push(dist[u].secBest + w)) pq.push({-dist[u].secBest - w, v});
    }
    return dist[0].secBest;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:57:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto [v, w] : adj[u])
      |                   ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3676 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3608 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 3 ms 3676 KB Output is correct
10 Correct 2 ms 3420 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 3 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 2 ms 3608 KB Output is correct
16 Correct 254 ms 58944 KB Output is correct
17 Correct 44 ms 14172 KB Output is correct
18 Correct 71 ms 15644 KB Output is correct
19 Correct 289 ms 61736 KB Output is correct
20 Correct 166 ms 50768 KB Output is correct
21 Correct 23 ms 8532 KB Output is correct
22 Correct 194 ms 46944 KB Output is correct