oj.uz

Submission #794555

# Submission time Handle Problem Language Result Execution time Memory
794555 2023-07-26T15:44:09 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 170096 KB 
#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,75);
  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 2772 KB Correct.
2 Correct 22 ms 2840 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3616 KB Correct.
2 Correct 27 ms 3612 KB Correct.
3 Correct 25 ms 3660 KB Correct.
4 Correct 25 ms 3652 KB Correct.
5 Correct 22 ms 3668 KB Correct.
6 Correct 23 ms 11764 KB Correct.
7 Correct 30 ms 11608 KB Correct.
8 Correct 19 ms 20940 KB Correct.
9 Correct 21 ms 2808 KB Correct.
10 Correct 20 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3568 KB Correct.
2 Correct 23 ms 3676 KB Correct.
3 Correct 22 ms 3700 KB Correct.
4 Correct 23 ms 2828 KB Correct.
5 Correct 22 ms 2772 KB Correct.
6 Correct 8 ms 10196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 61268 KB Correct.
2 Correct 293 ms 4024 KB Correct.
3 Correct 229 ms 4076 KB Correct.
4 Correct 248 ms 3996 KB Correct.
5 Correct 209 ms 2896 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3700 KB Correct.
2 Correct 21 ms 3632 KB Correct.
3 Correct 21 ms 3668 KB Correct.
4 Correct 29 ms 11940 KB Correct.
5 Correct 21 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3688 KB Correct.
2 Correct 21 ms 3728 KB Correct.
3 Correct 59 ms 72900 KB Correct.
4 Correct 18 ms 9428 KB Correct.
5 Correct 20 ms 2824 KB Correct.
6 Correct 20 ms 3624 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 4572 KB Correct.
2 Correct 38 ms 5924 KB Correct.
3 Correct 583 ms 93432 KB Correct.
4 Correct 480 ms 23568 KB Correct.
5 Correct 1010 ms 71504 KB Correct.
6 Correct 452 ms 48684 KB Correct.
7 Correct 470 ms 25560 KB Correct.
8 Correct 475 ms 6188 KB Correct.
9 Correct 203 ms 5120 KB Correct.
10 Correct 191 ms 4652 KB Correct.
11 Correct 456 ms 4104 KB Correct.
12 Correct 228 ms 4664 KB Correct.
13 Correct 249 ms 4612 KB Correct.
14 Correct 384 ms 47248 KB Correct.
15 Correct 442 ms 14956 KB Correct.
16 Correct 208 ms 4584 KB Correct.
17 Correct 264 ms 4548 KB Correct.
18 Correct 234 ms 4568 KB Correct.
19 Correct 544 ms 4496 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 16 ms 4008 KB Correct.
22 Correct 32 ms 6088 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 7576 KB Correct.
2 Correct 134 ms 11188 KB Correct.
3 Correct 613 ms 98196 KB Correct.
4 Correct 1061 ms 10440 KB Correct.
5 Execution timed out 3063 ms 170096 KB Time limit exceeded
6 Halted 0 ms 0 KB -