Submission #706694

#	Time	Username	Problem	Language	Result	Execution time	Memory
706694		Alihan_8	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	816 ms	68780 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
typedef long long ll;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    int n = N, m = M, k = K;
    vector <pair<ll,int>> g[n];
    for ( int i = 0; i < m; i++ ){
        auto [x, y] = R[i];
        g[x].pb({L[i], y});
        g[y].pb({L[i], x});
    }
    const ll inf = 1e18+1;
    set <pair<ll,ll>> st;
    vector <pair<ll,ll>> dis(n, {inf, inf});
    for ( int i = 0; i < k; i++ ){
        dis[P[i]] = {0, 0};
        st.insert({0, P[i]});
    }
    while ( !st.empty() ){
        auto [val, cur] = *st.begin();
        st.erase(st.begin());
        for ( auto [w, to]: g[cur] ){
            ll new_dis = val+w;
            auto &[l, r] = dis[to];
            if ( l > new_dis ){
                st.erase({r, to});
                r = l, l = new_dis;
                st.insert({r, to});
            }
            else if ( r > new_dis ){
                st.erase({r, to});
                r = new_dis;
                st.insert({r, to});
            }
        }
    }
    return dis[0].second;
}
#if false
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k; cin >> n >> m >> k;
    int R[m][2], L[m], p[k];
    for ( int i = 0; i < m; i++ ){
        cin >> R[i][0] >> R[i][1];
    }
    for ( int i = 0; i < m; i++ ) cin >> L[i];
    for ( int i = 0; i < k; i++ ) cin >> p[i];
    cout << travel_plan(n, m, R, L, k, p);

    cout << '\n';
/*
5 4 3
0 1
0 2
3 2
2 4
2 3 1 4
1 3 4
answer: 7

5 7 2
0 2
0 3
3 2
2 1
0 1
0 4
3 4
4 3 2 10 100 7 9
1 3
answer: 14
*/
}
#endif

Compilation message (stderr)

crocodile.cpp: In function 'void IO(std::string)':
crocodile.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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