oj.uz

Submission #625352

# Submission time Handle Problem Language Result Execution time Memory
625352 2022-08-10T06:23:57 Z EthanKim8683 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 497 ms 87440 KB 
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>

using namespace std;

using I=int;
using Lli=long long int;

// dijkstra's from all exits
// only push nodes once reachable from two exits

I travel_plan(I n,I m,I r[][2],I l[],I k,I p[]){
  vector<vector<pair<I,I>>>adjs(n);
  for(I i=0;i<m;i++){
    I a=r[i][0],b=r[i][1],d=l[i];
    adjs[a].push_back({b,d});
    adjs[b].push_back({a,d});
  }
  priority_queue<pair<Lli,I>>que;
  vector<I>viss(n,0);
  for(I i=0;i<k;i++){
    viss[p[i]]=2;
    for(auto[b,d]:adjs[p[i]])
      que.push({-d,b});
  }
  while(!que.empty()){
    auto[dis,a]=que.top();
    que.pop();
    if(viss[a]>=2)continue;
    if(++viss[a]!=2)continue;
    if(a==0)return -dis;
    for(auto[b,d]:adjs[a])
      que.push({dis-d,b});
  }
  return -1;
}

#ifdef ETHANKIM8683
#include<iostream>
#include<cstdio>

const I N=100000;
const I M=1000000;
const I K=999999;

I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;
  cin>>n>>m;
  static I r[M][2];
  for(I i=0;i<m;i++)cin>>r[i][0]>>r[i][1];
  static I l[M];
  for(I i=0;i<m;i++)cin>>l[i];
  I k;
  cin>>k;
  static I p[K];
  for(I i=0;i<k;i++)cin>>p[i];
  printf("%i\n",travel_plan(n,m,r,l,k,p));
  return 0;
}
#endif

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1240 KB Output is correct
13 Correct 3 ms 1384 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 1240 KB Output is correct
13 Correct 3 ms 1384 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 463 ms 87440 KB Output is correct
17 Correct 74 ms 13312 KB Output is correct
18 Correct 83 ms 14756 KB Output is correct
19 Correct 476 ms 75228 KB Output is correct
20 Correct 316 ms 79888 KB Output is correct
21 Correct 44 ms 5884 KB Output is correct
22 Correct 497 ms 45448 KB Output is correct