oj.uz

답안 #706693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706693 2023-03-07T11:38:44 Z Alihan_8 악어의 지하 도시 (IOI11_crocodile) C++17
89 / 100
 526 ms 76956 KB 
#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;
    priority_queue <pair<ll,int>> q;
    vector <pair<ll,ll>> dis(n, {inf, inf});
    for ( int i = 0; i < n; i++ ){
        q.push({-inf, i});
    }
    for ( int i = 0; i < k; i++ ){
        dis[P[i]] = {0, 0};
        q.push({0, P[i]});
    }
    while ( !q.empty() ){
        auto [val, cur] = q.top();
        q.pop(); val = -val;
        if ( val > dis[cur].second ) continue;
        for ( auto [w, to]: g[cur] ){
            ll new_dis = val+w;
            auto &[l, r] = dis[to];
            if ( l > new_dis ){
                r = l, l = new_dis;
                q.push({-r, to});
            }
            else if ( r > new_dis ){
                r = new_dis;
                q.push({-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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 340 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 340 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 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 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 340 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 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 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 396 ms 67532 KB Output is correct
17 Correct 97 ms 18636 KB Output is correct
18 Correct 118 ms 20824 KB Output is correct
19 Correct 526 ms 76956 KB Output is correct
20 Correct 252 ms 52812 KB Output is correct
21 Correct 41 ms 7756 KB Output is correct
22 Incorrect 280 ms 49340 KB Output isn't correct
23 Halted 0 ms 0 KB -