Submission #696114

#	Time	Username	Problem	Language	Result	Execution time	Memory
696114		jiahng	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1529 ms	105860 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0
vpi adj[maxn];
ll dist[maxn];
multiset <int> cost[maxn];

int32_t travel_plan(int32_t N, int32_t M, int32_t R[][2], int32_t L[], int32_t K, int32_t P[])
{
    FOR(i,0,M-1){
        adj[R[i][0]].pb(pi(R[i][1], L[i]));
        adj[R[i][1]].pb(pi(R[i][0], L[i]));
    }
    set <pi> st;
    mem(dist, -1);
    mem(cost, INF);
    FOR(i,0,K-1){
        st.insert(pi(0, P[i]));
        dist[P[i]] = 0;
    }
    FOR(i,0,N-1) cost[i].insert(INF);
    while (!st.empty()){
        pi cur = *st.begin(); st.erase(st.begin()); 
        //cout << cur.f << ' ' << cur.s << '\n';
        //if (cur.f == 4 && cur.s == 4) break;

        dist[cur.s] = cur.f;

        aFOR(i, adj[cur.s]) if (dist[i.f] == -1){
            st.erase(pi(*cost[i.f].rbegin(), i.f));
            cost[i.f].insert(cur.f + i.s);
            while (cost[i.f].size() > 2) cost[i.f].erase(--cost[i.f].end());
            st.insert(pi(*cost[i.f].rbegin(), i.f));
        }
    }
    
    return dist[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int32_t travel_plan(int32_t, int32_t, int32_t (*)[2], int32_t*, int32_t, int32_t*)':
crocodile.cpp:26:13: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   26 | #define INF (ll)1e18
      |             ^~~~~~~~
crocodile.cpp:23:27: note: in definition of macro 'mem'
   23 | #define mem(x,i) memset(x,i,sizeof x)
      |                           ^
crocodile.cpp:44:15: note: in expansion of macro 'INF'
   44 |     mem(cost, INF);
      |               ^~~
crocodile.cpp:23:37: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'class std::multiset<long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   23 | #define mem(x,i) memset(x,i,sizeof x)
      |                                     ^
crocodile.cpp:44:5: note: in expansion of macro 'mem'
   44 |     mem(cost, INF);
      |     ^~~
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from crocodile.cpp:2:
/usr/include/c++/10/bits/stl_multiset.h:96:11: note: 'class std::multiset<long long int>' declared here
   96 |     class multiset
      |           ^~~~~~~~

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