제출 #794907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794907		christinelynn	Cyberland (APIO23_cyberland)	C++17	21 / 100	332 ms	23532 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3