Submission #802677

#	Time	Username	Problem	Language	Result	Execution time	Memory
802677		Nelt	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	576 ms	101484 KiB

crocodile

// #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 (stderr)

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

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11