oj.uz

답안 #229791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229791 2020-05-06T14:13:26 Z quocnguyen1012 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 628 ms 61140 KB 
#ifndef LOCAL
#include "crocodile.h"
#endif // LOCAL

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const int inf = 2e9;

int N, M, K;
int dist[maxn][2];
vector<ii> adj[maxn];

int travel_plan(int _N, int _M, int R[][2], int L[], int _K, int P[])
{
  priority_queue<ii, vector<ii>, greater<ii>> pq;
  N = _N, M = _M, K = _K;
  for(int i = 0; i < M; ++i){
    adj[R[i][0]].eb(R[i][1], L[i]);
    adj[R[i][1]].eb(R[i][0], L[i]);
    ///cerr << R[i][0] << ' ' << R[i][1] << ' ' << L[i] << '\n';
  }
  fill_n(&dist[0][0], maxn * 2, inf);
  for(int i = 0; i < K; ++i){
    pq.push(mp(0, P[i]));
    dist[P[i]][0] = dist[P[i]][1] = 0;
  }
  while(pq.size()){
    int now; int u;
    tie(now, u) = pq.top(); pq.pop();
    if(now > dist[u][1]) continue;
    for(auto v : adj[u]){
      ll d = dist[u][1] + v.se;
      if(dist[v.fi][0] > d){
        swap(dist[v.fi][0], dist[v.fi][1]);
        dist[v.fi][0] = d;
        if(dist[v.fi][1] != inf)
          pq.push(mp(dist[v.fi][1], v.fi));
      }
      else if(dist[v.fi][1] > d){
        dist[v.fi][1] = d;
        pq.push(mp(d, v.fi));
      }
    }
    ///cerr << '\n';
  }
  return dist[0][1];
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int _N, _M, _K;
  cin >> _N >> _M >> _K;
  int L[_M], R[_M][2], 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);
}
#endif // LOCAL

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 8 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 8 ms 3456 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 8 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 10 ms 3968 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 8 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 8 ms 3456 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 8 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 7 ms 3712 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 10 ms 3968 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct
16 Correct 519 ms 57592 KB Output is correct
17 Correct 95 ms 13816 KB Output is correct
18 Correct 110 ms 15224 KB Output is correct
19 Correct 628 ms 61140 KB Output is correct
20 Correct 331 ms 50424 KB Output is correct
21 Correct 46 ms 8312 KB Output is correct
22 Incorrect 372 ms 46584 KB Output isn't correct