oj.uz

답안 #743672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743672 2023-05-17T16:37:31 Z Dan4Life 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 548 ms 63500 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using pii = pair<int,int>;
const int mxN = (int)1e5+10;
const int INF = (int)1e9;
vector<int> exits;
vector<pii> adj[mxN];
int n, m, dis[mxN], dis2[mxN], vis[mxN];

int dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    memset(dis,63,sizeof(dis)); memset(dis2,63,sizeof(dis2));
    for(auto u : exits) dis[u]=0, dis2[u]=0, pq.push({0,u});
    while(!pq.empty()){
        int s = pq.top().second; pq.pop();
        if(vis[s]) continue; vis[s]=1;
        for(auto cur : adj[s]){
            int u = cur.first, w = cur.second;
            if(dis[u]>dis2[s]+w){
                dis2[u]=dis[u], dis[u]=dis2[s]+w;
                pq.push({dis2[u],u});
            }
            else if(dis2[u]>dis2[s]+w)
                dis2[u]=dis2[s]+w, pq.push({dis2[u],u});
        }

    }
    return dis2[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int k, int p[])
{
    n = N, m = M;
    for(int i = 0; i < m; i++){
        int a = R[i][0], b = R[i][1], c = L[i];
        adj[a].pb({b,c}), adj[b].pb({a,c});
    }
    for(int i = 0; i < k; i++) exits.pb(p[i]);
    return dijkstra();
}

Compilation message

crocodile.cpp: In function 'int dijkstra()':
crocodile.cpp:19:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |         if(vis[s]) continue; vis[s]=1;
      |         ^~
crocodile.cpp:19:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |         if(vis[s]) continue; vis[s]=1;
      |                              ^~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 8 ms 3924 KB Output is correct
13 Correct 7 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 4 ms 3476 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 4 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 8 ms 3924 KB Output is correct
13 Correct 7 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 4 ms 3476 KB Output is correct
16 Correct 381 ms 58932 KB Output is correct
17 Correct 94 ms 15176 KB Output is correct
18 Correct 100 ms 16784 KB Output is correct
19 Correct 548 ms 63500 KB Output is correct
20 Correct 263 ms 50348 KB Output is correct
21 Correct 40 ms 8680 KB Output is correct
22 Correct 260 ms 46948 KB Output is correct