oj.uz

Submission #800377

# Submission time Handle Problem Language Result Execution time Memory
800377 2023-08-01T13:53:28 Z Boomyday Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 397 ms 112616 KB 

//
// Created by adavy on 3/3/2023.
//
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)


#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!


#include "crocodile.h"
/*
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
    int i;
    my_assert(3==scanf("%d %d %d",&N,&M,&K));
    for(i=0; i<M; i++)
        my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
    for(i=0; i<K; i++)
        my_assert(1==scanf("%d",&P[i]));
    my_assert(1==scanf("%d",&solution));
}*/
vl dist;
vl dist2;
vi vis;
vi par;
vector<vector<pair<ll,int>>> adj;


/*
void dfs(int nd){
    vis[nd] = 1;
    if (adj[nd].size() == 1){
         dist[nd] = 0;
         par[nd] = adj[nd][0].s;
         return;
    }

    trav(nei, adj[nd]){ if (!vis[nei.s]) dfs(nei.s); else par[nd] = nei.s;}
    ll bst = INF, sbst = INF;
    for(auto&[len, nei]:adj[nd]){
        if (nei == par[nd]) continue;
        ll distN = dist[nei] + len;
        if (distN < bst) {
            sbst = bst; bst = distN;
        }
        else if (distN < sbst) {
            sbst = distN;
        }
    }
    dist[nd] = sbst;


}
*/
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    adj.rsz(n);
    vis.rsz(n);
    dist.rsz(n);
    dist2.rsz(n);
    par.rsz(n);
    fill(all(vis),0);
    fill(all(dist),INF);
    fill(all(dist2),INF);
    F0R(i, k){
        dist[p[i]] = 0;
        dist2[p[i]] = 0;
    }


    F0R(i, m){
        adj[r[i][0]].pb({l[i], r[i][1]});
        adj[r[i][1]].pb({l[i], r[i][0]});
    }


    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> hp;


    F0R(i, k){ hp.push ({dist2[p[i]], p[i]});

    }
    F0R(i, k){ hp.push ({dist2[p[i]], p[i]});

    }



    while(!hp.empty()){

        //cout << "sz" << " " << hp.size() << endl;
         auto [cost, nd] = hp.top(); hp.pop();
        vis[nd]++;

        //cout << nd << " " << cost << " " << vis[nd] <<  endl;
        //trav(i, dist2) cout << i << " "; cout << endl;

        if (vis[nd] == 1 or vis[nd] > 2) continue;
        else{
            dist2[nd] = cost;
            if (nd==0){
                return cost;
            }
            for (auto& [len, nei]:adj[nd]) {
                if (vis[nei] > 2) continue;
                hp.push({dist2[nd]+len, nei});
            }
        }



    }



    /*

    dfs(0);


     */





}
/*

int main()
{
    int ans;
    read_input();
    ans = travel_plan(N,M,R,L,K,P);
    if(ans==solution)
        printf("Correct.\n");
    else
        printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

    return 0;
}





*/

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:149:82: warning: control reaches end of non-void function [-Wreturn-type]
  149 |     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> hp;
      |                                                                                  ^~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 468 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 448 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 0 ms 304 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 468 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 448 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 448 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 0 ms 304 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 468 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 448 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 448 KB Output is correct
16 Correct 380 ms 112616 KB Output is correct
17 Correct 84 ms 18336 KB Output is correct
18 Correct 73 ms 20836 KB Output is correct
19 Correct 397 ms 102340 KB Output is correct
20 Correct 228 ms 65356 KB Output is correct
21 Correct 32 ms 8336 KB Output is correct
22 Correct 378 ms 63352 KB Output is correct