oj.uz

Submission #794560

# Submission time Handle Problem Language Result Execution time Memory
794560 2023-07-26T15:46:31 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
97 / 100
 1115 ms 97264 KB 
#pragma GCC optimize("Ofast")
#include "cyberland.h"

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const double eps=1e-8;
const int maxn=1e5+10;
const double inf=1e15;
const int maxk=110;

int n,m,k,h;
vector<pair<int,int> > g[maxn];
double dist[maxn][maxk];
bool bio[maxn];

void dfs(int node){
  if(bio[node]) return;
  bio[node]=true;
  for(auto [i,c]:g[node]){
    if(bio[i]) continue;
    dfs(i);
  }
}

double solve(int _n,int _m,int _k, int _h,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){
  n=_n; m=_m; k=_k; h=_h;
  k=min(k,45);
  for(int i=0;i<n;i++) g[i].clear();
  for(int i=0;i<n;i++) bio[i]=false;
  for(int i=0;i<n;i++) for(int j=0;j<=k;j++) dist[i][j]=inf;
  for(int i=0;i<m;i++){
    if(x[i]==h || y[i]==h) continue;
    g[x[i]].push_back({y[i],c[i]});
    g[y[i]].push_back({x[i],c[i]});
  }

  dfs(0);

  bool moze=false;
  for(int i=0;i<m;i++){
    if(x[i]==h || y[i]==h){
      if(bio[x[i]] || bio[y[i]]) moze=true;
    }
  }
  if(!moze) return -1;

  priority_queue<tuple<double,int,int> > pq;
  pq.push({0,0,0});
  dist[0][0]=0;
  for(int i=0;i<n;i++){
    if(arr[i]==0 && bio[i]){
      pq.push({0,i,0});
      dist[i][0]=0;
    }
  }
  while(!pq.empty()){
    auto [cost,node,delio]=pq.top();
    pq.pop();
    cost=-cost;
    if(cost>dist[node][delio]/*-eps*/) continue;
    for(auto [i,c]:g[node]){
      if(arr[i]==2){
        if(cost+c<dist[i][delio]-eps){
          dist[i][delio]=cost+c;
          pq.push({-dist[i][delio],i,delio});
        }
        if(delio<k && cost+c<2*dist[i][delio+1]-eps){
          dist[i][delio+1]=(cost+c)/2;
          pq.push({-dist[i][delio+1],i,delio+1});
        }
      }else{
        if(cost+c<dist[i][delio]-eps){
          dist[i][delio]=cost+c;
          pq.push({-dist[i][delio],i,delio});
        }
      }
    }
  }

  double ret=inf;
  for(int i=0;i<m;i++){
    if(x[i]==h || y[i]==h){
      if(x[i]!=h) for(int j=0;j<=k;j++) ret=min(ret,dist[x[i]][j]+c[i]);
      if(y[i]!=h) for(int j=0;j<=k;j++) ret=min(ret,dist[y[i]][j]+c[i]);
    }
  }
  return ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2904 KB Correct.
2 Correct 16 ms 3076 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4028 KB Correct.
2 Correct 29 ms 4580 KB Correct.
3 Correct 27 ms 4496 KB Correct.
4 Correct 23 ms 4508 KB Correct.
5 Correct 22 ms 4588 KB Correct.
6 Correct 23 ms 12588 KB Correct.
7 Correct 30 ms 12520 KB Correct.
8 Correct 26 ms 21260 KB Correct.
9 Correct 20 ms 3540 KB Correct.
10 Correct 21 ms 3532 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4532 KB Correct.
2 Correct 24 ms 4472 KB Correct.
3 Correct 22 ms 4460 KB Correct.
4 Correct 22 ms 3076 KB Correct.
5 Correct 24 ms 3596 KB Correct.
6 Correct 11 ms 10452 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 62052 KB Correct.
2 Correct 271 ms 4048 KB Correct.
3 Correct 233 ms 4080 KB Correct.
4 Correct 258 ms 3988 KB Correct.
5 Correct 213 ms 2904 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4564 KB Correct.
2 Correct 21 ms 4564 KB Correct.
3 Correct 21 ms 4600 KB Correct.
4 Correct 27 ms 12800 KB Correct.
5 Correct 19 ms 3516 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4500 KB Correct.
2 Correct 18 ms 4436 KB Correct.
3 Correct 69 ms 74316 KB Correct.
4 Correct 17 ms 9864 KB Correct.
5 Correct 20 ms 3656 KB Correct.
6 Correct 21 ms 4224 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 5420 KB Correct.
2 Correct 41 ms 5944 KB Correct.
3 Correct 620 ms 93256 KB Correct.
4 Correct 562 ms 23604 KB Correct.
5 Correct 1115 ms 71316 KB Correct.
6 Correct 445 ms 48524 KB Correct.
7 Correct 454 ms 25532 KB Correct.
8 Correct 464 ms 6176 KB Correct.
9 Correct 202 ms 5172 KB Correct.
10 Correct 190 ms 4620 KB Correct.
11 Correct 473 ms 4156 KB Correct.
12 Correct 228 ms 4636 KB Correct.
13 Correct 247 ms 4668 KB Correct.
14 Correct 421 ms 47140 KB Correct.
15 Correct 464 ms 15004 KB Correct.
16 Correct 205 ms 4548 KB Correct.
17 Correct 276 ms 4500 KB Correct.
18 Correct 235 ms 4500 KB Correct.
19 Correct 545 ms 4492 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 17 ms 4008 KB Correct.
22 Correct 42 ms 6040 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 6156 KB Correct.
2 Correct 64 ms 7588 KB Correct.
3 Incorrect 433 ms 97264 KB Wrong Answer.
4 Halted 0 ms 0 KB -