oj.uz

Submission #891762

# Submission time Handle Problem Language Result Execution time Memory
891762 2023-12-24T03:05:27 Z vjudge1 Relay Marathon (NOI20_relaymarathon) C++14
25 / 100
 1235 ms 181876 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(a) (a).begin(), (a).end()

const int N=1e5+1;
int n, m, k, dd[N];
int dist[N], par[N], d1[N], d2[N];
vector<pair<int, int>> g[N];

pair<pair<int, int>, pair<int, int>> dijkstra(int root, int d[]){
   memset(d, 0, sizeof(int)*N);
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   d[root]=0;
   pq.emplace(d[root], root);
   pair<pair<int, int>, pair<int, int>> ans={{1e18, -1}, {1e18, -1}};
   while (pq.size()){
      int u=pq.top().second, f=pq.top().first;
      pq.pop();
      if (d[u]!=f) continue;
      if (u!=root && dd[u]){
         if (ans.first.first>dist[u]){
            ans.second=ans.first;
            ans.first={dist[u], u};
         }else ans.second=min(ans.second, {dist[u], u});
      }
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (d[v]>d[u]+w){
            d[v]=d[u]+w;
            pq.emplace(d[v], v);
         }
      }
   }
   return ans;
}

pair<int, pair<int, int>> dijkstra(vector<int> root){
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   memset(dist, 0x3f, sizeof dist);
   for (int x:root){
      dist[x]=0; par[x]=x;
      pq.emplace(dist[x], x);
   }
   pair<int, pair<int, int>> best={-1, {-1, -1}};
   while (pq.size()){
      int u=pq.top().second, d=pq.top().first; pq.pop();
      if (dist[u]!=d) continue;
      for (auto &e:g[u]){
         int v=e.first, w=e.second;
         if (par[u]!=par[v]){
            if (best.first==-1) best={dist[u]+dist[v]+w, {par[u], par[v]}};
            else best=min(best, {dist[u]+dist[v]+w, {par[u], par[v]}});
         }
         if (dist[v]>dist[u]+w){
            dist[v]=dist[u]+w;
            par[v]=par[u];
            pq.emplace(dist[v], v);
         }
      }
   }
   return best;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m >> k;
   for (int i=1; i<=m; ++i){
      int u, v, w; cin >> u >> v >> w;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
   }
   vector<int> v(k);
   for (int &i:v) cin >> i, dd[i]=1;
   auto best1=dijkstra(v);
   int t1=best1.second.first, t2=best1.second.second;
   v.erase(find(all(v), t1));
   v.erase(find(all(v), t2));
   auto g1=dijkstra(t1, d1);
   auto g2=dijkstra(t2, d2);
   auto best2=dijkstra(v);
   int ans=best1.first+best2.first;
   if (g1.first.second!=-1 && g2.first.second!=-1 && g1.first.second!=g2.first.second){
      ans=min(ans, g1.first.first+g2.first.first);
   }
   if (g1.first.second!=-1 && g2.second.second!=-1 && g1.first.second!=g2.second.second){
      ans=min(ans, g1.first.first+g2.second.first);
   }
   if (g1.second.second!=-1 && g2.first.second!=-1 && g1.second.second!=g2.first.second){
      ans=min(ans, g1.second.first+g2.first.first);
   }
   cout << ans;
   return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11212 KB Output is correct
2 Correct 3 ms 6232 KB Output is correct
3 Correct 1119 ms 163080 KB Output is correct
4 Correct 494 ms 79712 KB Output is correct
5 Correct 110 ms 19204 KB Output is correct
6 Correct 84 ms 16004 KB Output is correct
7 Correct 141 ms 20700 KB Output is correct
8 Correct 50 ms 11156 KB Output is correct
9 Correct 72 ms 15208 KB Output is correct
10 Correct 54 ms 12560 KB Output is correct
11 Correct 1119 ms 172236 KB Output is correct
12 Correct 67 ms 13564 KB Output is correct
13 Correct 295 ms 49864 KB Output is correct
14 Correct 148 ms 21820 KB Output is correct
15 Correct 1054 ms 170040 KB Output is correct
16 Correct 28 ms 10076 KB Output is correct
17 Correct 763 ms 122316 KB Output is correct
18 Correct 4 ms 6492 KB Output is correct
19 Correct 1235 ms 181876 KB Output is correct
20 Correct 109 ms 20848 KB Output is correct
21 Correct 102 ms 18228 KB Output is correct
22 Correct 46 ms 12332 KB Output is correct
23 Correct 22 ms 9108 KB Output is correct
24 Correct 742 ms 134236 KB Output is correct
25 Correct 90 ms 15428 KB Output is correct
26 Correct 39 ms 11088 KB Output is correct
27 Correct 61 ms 13620 KB Output is correct
28 Correct 8 ms 7768 KB Output is correct
29 Correct 173 ms 20416 KB Output is correct
30 Correct 252 ms 39044 KB Output is correct

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -