oj.uz

Submission #794608

# Submission time Handle Problem Language Result Execution time Memory
794608 2023-07-26T16:22:36 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
100 / 100
 2861 ms 104084 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];

inline bool raz(const double a,const double b){
  return abs(a-b)/max(double(1),b)<=eps;
}

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,66);
  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(!raz(cost+c,dist[i][delio]) && cost+c<dist[i][delio]){
          dist[i][delio]=cost+c;
          pq.push({-dist[i][delio],i,delio});
        }
        if(delio<k && !raz((cost+c)/2,dist[i][delio+1]) && cost+c<2*dist[i][delio+1]){
          dist[i][delio+1]=(cost+c)/2;
          pq.push({-dist[i][delio+1],i,delio+1});
        }
      }else{
        if(!raz(cost+c,dist[i][delio]) && cost+c<dist[i][delio]){
          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 15 ms 2772 KB Correct.
2 Correct 15 ms 2760 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3624 KB Correct.
2 Correct 23 ms 3632 KB Correct.
3 Correct 21 ms 3592 KB Correct.
4 Correct 22 ms 3668 KB Correct.
5 Correct 25 ms 3692 KB Correct.
6 Correct 23 ms 11860 KB Correct.
7 Correct 29 ms 11572 KB Correct.
8 Correct 19 ms 20940 KB Correct.
9 Correct 21 ms 2772 KB Correct.
10 Correct 20 ms 2824 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3568 KB Correct.
2 Correct 24 ms 3672 KB Correct.
3 Correct 29 ms 3688 KB Correct.
4 Correct 28 ms 2716 KB Correct.
5 Correct 28 ms 2808 KB Correct.
6 Correct 10 ms 10196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 60992 KB Correct.
2 Correct 261 ms 4052 KB Correct.
3 Correct 233 ms 4064 KB Correct.
4 Correct 242 ms 4016 KB Correct.
5 Correct 203 ms 2888 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3668 KB Correct.
2 Correct 22 ms 3724 KB Correct.
3 Correct 22 ms 3668 KB Correct.
4 Correct 23 ms 11864 KB Correct.
5 Correct 17 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3824 KB Correct.
2 Correct 18 ms 3692 KB Correct.
3 Correct 57 ms 73004 KB Correct.
4 Correct 16 ms 9408 KB Correct.
5 Correct 19 ms 2772 KB Correct.
6 Correct 20 ms 3668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 4540 KB Correct.
2 Correct 37 ms 5916 KB Correct.
3 Correct 651 ms 93332 KB Correct.
4 Correct 476 ms 23552 KB Correct.
5 Correct 999 ms 71332 KB Correct.
6 Correct 432 ms 48596 KB Correct.
7 Correct 453 ms 25432 KB Correct.
8 Correct 462 ms 6200 KB Correct.
9 Correct 198 ms 5184 KB Correct.
10 Correct 187 ms 4596 KB Correct.
11 Correct 454 ms 4136 KB Correct.
12 Correct 228 ms 4624 KB Correct.
13 Correct 239 ms 4644 KB Correct.
14 Correct 399 ms 47148 KB Correct.
15 Correct 461 ms 14928 KB Correct.
16 Correct 204 ms 4516 KB Correct.
17 Correct 267 ms 4560 KB Correct.
18 Correct 227 ms 4568 KB Correct.
19 Correct 550 ms 4504 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 17 ms 4004 KB Correct.
22 Correct 33 ms 6088 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 6764 KB Correct.
2 Correct 85 ms 7912 KB Correct.
3 Correct 508 ms 97320 KB Correct.
4 Correct 786 ms 10088 KB Correct.
5 Correct 2410 ms 104084 KB Correct.
6 Correct 1153 ms 82852 KB Correct.
7 Correct 889 ms 38888 KB Correct.
8 Correct 900 ms 6492 KB Correct.
9 Correct 510 ms 7096 KB Correct.
10 Correct 473 ms 7600 KB Correct.
11 Correct 1275 ms 3988 KB Correct.
12 Correct 545 ms 7828 KB Correct.
13 Correct 598 ms 7728 KB Correct.
14 Correct 2861 ms 90744 KB Correct.
15 Correct 2324 ms 54860 KB Correct.
16 Correct 1417 ms 24884 KB Correct.
17 Correct 1056 ms 9192 KB Correct.
18 Correct 512 ms 7116 KB Correct.
19 Correct 657 ms 6652 KB Correct.
20 Correct 590 ms 6468 KB Correct.
21 Correct 1443 ms 5624 KB Correct.
22 Correct 43 ms 3568 KB Correct.
23 Correct 39 ms 5016 KB Correct.
24 Correct 79 ms 12168 KB Correct.