oj.uz

Submission #411883

# Submission time Handle Problem Language Result Execution time Memory
411883 2021-05-26T07:49:25 Z pliam Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 628 ms 77608 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF (ll)1e18+5
typedef long long ll;
typedef pair<ll,int> pli;//(d2[x],x);

//Dijkstra
ll d1[MAXN],d2[MAXN];
bool used[MAXN];
vector<pair<int,ll>> adj[MAXN];//(to,weight)
priority_queue<pli,vector<pli>,greater<pli>> q;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i=0;i<M;i++){
    adj[R[i][0]].push_back({R[i][1],L[i]});
    adj[R[i][1]].push_back({R[i][0],L[i]});
  }
  for(int i=0;i<N;i++){
    d1[i]=d2[i]=INF;
    used[i]=false;
  }
  for(int i=0;i<K;i++){
    d1[P[i]]=d2[P[i]]=0;
    q.push({d2[P[i]],P[i]});
  }
  while(!q.empty()){
    int v=q.top().second;
    q.pop();
    if(used[v]) continue;
    used[v]=true;
    for(auto p:adj[v]){
      int to=p.first;
      ll w=p.second;
      if(d2[v]+w<=d1[to]){
        d2[to]=d1[to];
        d1[to]=d2[v]+w;
      }else if(d2[v]+w<d2[to]){
        d2[to]=d2[v]+w;
      }else{
        continue;//d2[to] didn't change
      }
      q.push({d2[to],to});
    }
  }
  return d2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 3 ms 2788 KB Output is correct
12 Correct 6 ms 3404 KB Output is correct
13 Correct 6 ms 3432 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 3 ms 2788 KB Output is correct
12 Correct 6 ms 3404 KB Output is correct
13 Correct 6 ms 3432 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 486 ms 69248 KB Output is correct
17 Correct 101 ms 16976 KB Output is correct
18 Correct 131 ms 19228 KB Output is correct
19 Correct 628 ms 77608 KB Output is correct
20 Correct 305 ms 55492 KB Output is correct
21 Correct 47 ms 9280 KB Output is correct
22 Correct 408 ms 50884 KB Output is correct