oj.uz

답안 #630420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630420 2022-08-16T10:48:34 Z NintsiChkhaidze 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 553 ms 81924 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define pb push_back
#define ll long long
#define f first
 
const int nn = 300005;
vector <pair<int,ll> > v[nn];
pair<ll,ll> dis[nn];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for (int i = 0; i < M; i++){
        v[R[i][0]].pb({R[i][1],L[i]});
        v[R[i][1]].pb({R[i][0],L[i]});
    }
    for (int i=0;i<N; i++)
        dis[i] = {1e18,1e18};
 
    using T = pair<ll,int>;
    priority_queue <T, vector <T>, greater <T>> pq;
    for (int i = 0; i < K; i++)
        dis[P[i]] = {0LL,0LL},pq.push({0LL,P[i]});
 
    while(pq.size()){
        ll d = pq.top().f;
        int x = pq.top().s;
        pq.pop();
        if (d != dis[x].s) continue;
        for (auto [to,w]: v[x]){
            ll vl = w + d;
            if (dis[to].f > vl) {
                dis[to].s = dis[to].f;
                dis[to].f = vl;
                pq.push({dis[to].s, to});
            }else if (dis[to].s > vl){
                dis[to].s = vl;
                pq.push({dis[to].s, to});
            }
            
        }
    }
    return dis[0].s;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         for (auto [to,w]: v[x]){
      |                   ^

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 7 ms 7764 KB Output is correct
10 Correct 5 ms 7368 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 8 ms 8180 KB Output is correct
13 Correct 7 ms 8144 KB Output is correct
14 Correct 6 ms 7380 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 7 ms 7764 KB Output is correct
10 Correct 5 ms 7368 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 8 ms 8180 KB Output is correct
13 Correct 7 ms 8144 KB Output is correct
14 Correct 6 ms 7380 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 384 ms 73800 KB Output is correct
17 Correct 87 ms 21512 KB Output is correct
18 Correct 115 ms 23716 KB Output is correct
19 Correct 553 ms 81924 KB Output is correct
20 Correct 256 ms 60108 KB Output is correct
21 Correct 40 ms 13852 KB Output is correct
22 Incorrect 271 ms 55408 KB Output isn't correct
23 Halted 0 ms 0 KB -