oj.uz

Submission #696114

# Submission time Handle Problem Language Result Execution time Memory
696114 2023-02-05T14:04:51 Z jiahng Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1529 ms 105860 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 10 ms 15956 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 10 ms 16084 KB Output is correct
6 Correct 9 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 9 ms 16060 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 10 ms 15956 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 10 ms 16084 KB Output is correct
6 Correct 9 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 9 ms 16060 KB Output is correct
9 Correct 10 ms 16316 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 16084 KB Output is correct
12 Correct 14 ms 16596 KB Output is correct
13 Correct 13 ms 16724 KB Output is correct
14 Correct 10 ms 15956 KB Output is correct
15 Correct 9 ms 16112 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 10 ms 15956 KB Output is correct
3 Correct 8 ms 16004 KB Output is correct
4 Correct 9 ms 16084 KB Output is correct
5 Correct 10 ms 16084 KB Output is correct
6 Correct 9 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 9 ms 16060 KB Output is correct
9 Correct 10 ms 16316 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 16084 KB Output is correct
12 Correct 14 ms 16596 KB Output is correct
13 Correct 13 ms 16724 KB Output is correct
14 Correct 10 ms 15956 KB Output is correct
15 Correct 9 ms 16112 KB Output is correct
16 Correct 1060 ms 93868 KB Output is correct
17 Correct 100 ms 38700 KB Output is correct
18 Correct 179 ms 40636 KB Output is correct
19 Correct 1529 ms 105860 KB Output is correct
20 Correct 461 ms 81372 KB Output is correct
21 Correct 60 ms 25336 KB Output is correct
22 Correct 460 ms 79660 KB Output is correct