oj.uz

Submission #802677

# Submission time Handle Problem Language Result Execution time Memory
802677 2023-08-02T13:17:22 Z Nelt Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 576 ms 101484 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,fma")

// #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// /* DEFINES */
// #define S second
// #define F first
// #define ll long long
// #define ull unsigned long long
// #define ld long double
// #define npos ULLONG_MAX
// #define INF LLONG_MAX
// #define vv(a) vector<a>
// #define pp(a, b) pair<a, b>
// #define pq(a) priority_queue<a>
// #define qq(a) queue<a>
// #define ss(a) set<a>
// #define mm(a, b) map<a, b>
// #define ump(a, b) unordered_map<a, b>
// #define ANDROID                   \
//     ios_base::sync_with_stdio(0); \
//     cin.tie(0);                   \
//     cout.tie(0);
// #define elif else if
// #define endl "\n"
// #define allc(a) begin(a), end(a)
// #define all(a) a, a + sizeof(a) / sizeof(a[0])
// #define pb push_back
// #define logi(a) __lg(a)
// #define sqrt(a) sqrtl(a)
// #define mpr make_pair
// #define ins insert
// using namespace std;
// using namespace __gnu_pbds;
// using namespace __cxx11;
// typedef char chr;
// typedef basic_string<chr> str;
// template <typename T, typename key = less<T>>
// using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// void solve()
// {

// }
// /*

// */
// int main()
// {
//     ANDROID
//     // precomp();
//     ll t = 1;
//     cin >> t;
//     for (ll i = 1; i <= t; i++)
//         // cout << "Case #" << i << ": ",
//         solve();
//     cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
// }
#include "crocodile.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int travel_plan(int n, int m, int R[][2], int L[], int k, int p[])
{
    vv(pp(ll, ll)) g[n];
    ll dist[n], cnt[n];
    for (ll i = 0; i < n; i++)
        dist[i] = 1e18, cnt[i] = 0;
    for (ll i = 0; i < m; i++)
        g[R[i][0]].pb(mpr(L[i], R[i][1])), g[R[i][1]].pb(mpr(L[i], R[i][0]));
    priority_queue<pp(ll, ll), vv(pp(ll, ll)), greater<>> q;
    for (ll i = 0; i < k; i++)
        dist[p[i]] = 0, cnt[p[i]] = 1, q.push(mpr(0, p[i]));
    while (!q.empty())
    {
        auto [tmp, v] = q.top();
        q.pop();
        cnt[v]++;
        if (cnt[v] != 2 or dist[v] < tmp)
            continue;
        dist[v] = tmp;
        for (auto [w, to] : g[v])
            if (cnt[to] < 2)
                q.push(mpr(dist[v] + w, to));
    }
    return dist[0];
}

Compilation message

crocodile.cpp:23:1: warning: multi-line comment [-Wcomment]
   23 | // #define ANDROID                   \
      | ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 6 ms 1364 KB Output is correct
13 Correct 4 ms 1492 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 6 ms 1364 KB Output is correct
13 Correct 4 ms 1492 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 562 ms 95800 KB Output is correct
17 Correct 65 ms 17612 KB Output is correct
18 Correct 95 ms 20012 KB Output is correct
19 Correct 576 ms 101484 KB Output is correct
20 Correct 395 ms 82212 KB Output is correct
21 Correct 39 ms 8116 KB Output is correct
22 Correct 330 ms 62924 KB Output is correct