oj.uz

Submission #986817

# Submission time Handle Problem Language Result Execution time Memory
986817 2024-05-21T09:32:27 Z huutuan Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 441 ms 96580 KB 
#include "crocodile.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e5+10, inf=1e18;
int n, m, vis[N];
pair<int, int> f[N][2];
vector<pair<int, int>> g[N];

void optimize(int i, pair<int, int> x){
   if (x.second==f[i][0].second || x.second==f[i][1].second){
      if (x.second==f[i][0].second) f[i][0].first=min(f[i][0].first, x.first);
      else f[i][1].first=min(f[i][1].first, x.first);
      if (f[i][0]>f[i][1]) swap(f[i][0], f[i][1]);
      return;
   }
   if (x<f[i][0]) f[i][1]=f[i][0], f[i][0]=x;
   else f[i][1]=min(f[i][1], x);
}

int32_t travel_plan(int32_t _N, int32_t M, int32_t R[][2], int32_t L[], int32_t K, int32_t P[])
{
   n=_N, m=M;
   for (int i=0; i<m; ++i){
      int u=R[i][0]+1, v=R[i][1]+1, w=L[i];
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
   }
   for (int i=1; i<=n; ++i) f[i][0]=f[i][1]={inf, -1};
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   for (int i=0; i<K; ++i){
      int u=P[i]+1;
      f[u][0]=f[u][1]={0, u};
      pq.emplace(0, u);
   }
   while (pq.size()){
      int u=pq.top().second; pq.pop();
      if (vis[u]) continue;
      vis[u]=1;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         pair<int, int> tmp[2]={f[v][0], f[v][1]};
         optimize(v, {f[u][1].first+w, u});
         if (tmp[0]!=f[v][0] || tmp[1]!=f[v][1]) pq.emplace(f[v][1].first, v);
      }
   }
   return f[1][1].first;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 11092 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10900 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 11092 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10900 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 5 ms 11356 KB Output is correct
13 Correct 4 ms 11356 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 11092 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10900 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 5 ms 11356 KB Output is correct
13 Correct 4 ms 11356 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 363 ms 88916 KB Output is correct
17 Correct 72 ms 24004 KB Output is correct
18 Correct 91 ms 26316 KB Output is correct
19 Correct 441 ms 96580 KB Output is correct
20 Correct 221 ms 72652 KB Output is correct
21 Correct 37 ms 17088 KB Output is correct
22 Correct 284 ms 67188 KB Output is correct