oj.uz

Submission #794907

# Submission time Handle Problem Language Result Execution time Memory
794907 2023-07-27T02:57:57 Z christinelynn Cyberland (APIO23_cyberland) C++17
21 / 100
 332 ms 23532 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> par, sz;
int find(int x) {return par[x]==x ? x : par[x]=find(par[x]);}
void join(int x, int y) {
  x=find(x); y=find(y);
  if(sz[x]<sz[y]) swap(x, y);
  sz[x]+=sz[y];
  par[y]=x;
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
  k=min(k, 100); double INF=1e18;
  par.resize(n); sz.resize(n);
  for(int i=0; i<n; i++) par[i]=i, sz[i]=1;
  vector<vector<pair<int, double>>> adj(n);
  for(int i=0; i<m; i++) {
    adj[x[i]].push_back({y[i], c[i]});
    adj[y[i]].push_back({x[i], c[i]});
    if(x[i]!=h && y[i]!=h) join(x[i], y[i]);
  }
  priority_queue<tuple<double, int, int>> pq;
  vector<vector<double>> dist(n, vector<double>(k+1)); for(auto &p : dist) for(double &pp : p) pp=INF;
  dist[h][0]=0; pq.push({0, 0, h});
  double ans=1e18;
  while(!pq.empty()) {
    double cur=get<0>(pq.top());
    int div=get<1>(pq.top()), u=get<2>(pq.top());
    pq.pop(); cur=-cur;
    if(dist[u][div]!=cur) continue;
    if(a[u]==2 && div<k) div++;
    if(u==0 || (a[u]==0 && par[u]==par[0])) {ans=min(ans, cur); continue;}
    if(a[u]==0) continue;
    for(auto p : adj[u]) {
      double edge=p.second;
      for(int i=0; i<div; i++) edge=edge/2.;
      if(dist[p.first][div]>cur+edge) {
        dist[p.first][div]=cur+edge;
        pq.push({-dist[p.first][div], div, p.first});
      }
    }
  }
  return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 568 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1060 KB Correct.
2 Correct 24 ms 1664 KB Correct.
3 Correct 28 ms 1636 KB Correct.
4 Correct 24 ms 1484 KB Correct.
5 Correct 23 ms 1564 KB Correct.
6 Correct 21 ms 4848 KB Correct.
7 Correct 26 ms 4996 KB Correct.
8 Correct 18 ms 8244 KB Correct.
9 Correct 24 ms 1136 KB Correct.
10 Correct 24 ms 1196 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1528 KB Correct.
2 Correct 22 ms 1496 KB Correct.
3 Correct 20 ms 1600 KB Correct.
4 Correct 23 ms 692 KB Correct.
5 Correct 27 ms 1212 KB Correct.
6 Correct 5 ms 3540 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23532 KB Correct.
2 Incorrect 22 ms 1520 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1516 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1512 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 1532 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 1936 KB Wrong Answer.
2 Halted 0 ms 0 KB -