Submission #800377

#	Time	Username	Problem	Language	Result	Execution time	Memory
800377		Boomyday	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	397 ms	112616 KiB

crocodile

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

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11