oj.uz

Submission #794615

# Submission time Handle Problem Language Result Execution time Memory
794615 2023-07-26T16:30:08 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
100 / 100
 2671 ms 183432 KB 
#pragma GCC optimize("Ofast")
#include "cyberland.h"

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const double eps=1e-7;
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];
double uradio[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]=uradio[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]) continue;
    if(raz(uradio[node][delio],dist[node][delio])) continue;
    uradio[node][delio]=dist[node][delio];
    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 22 ms 2748 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4500 KB Correct.
2 Correct 23 ms 4548 KB Correct.
3 Correct 22 ms 4436 KB Correct.
4 Correct 25 ms 4536 KB Correct.
5 Correct 34 ms 4484 KB Correct.
6 Correct 27 ms 20180 KB Correct.
7 Correct 37 ms 19944 KB Correct.
8 Correct 28 ms 37824 KB Correct.
9 Correct 20 ms 2904 KB Correct.
10 Correct 20 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4480 KB Correct.
2 Correct 26 ms 4540 KB Correct.
3 Correct 25 ms 4568 KB Correct.
4 Correct 24 ms 2916 KB Correct.
5 Correct 27 ms 2912 KB Correct.
6 Correct 12 ms 17108 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 111224 KB Correct.
2 Correct 269 ms 4876 KB Correct.
3 Correct 233 ms 4884 KB Correct.
4 Correct 250 ms 4824 KB Correct.
5 Correct 204 ms 2932 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4576 KB Correct.
2 Correct 23 ms 4472 KB Correct.
3 Correct 24 ms 4564 KB Correct.
4 Correct 32 ms 20188 KB Correct.
5 Correct 19 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4584 KB Correct.
2 Correct 19 ms 4572 KB Correct.
3 Correct 83 ms 138036 KB Correct.
4 Correct 21 ms 15220 KB Correct.
5 Correct 25 ms 2900 KB Correct.
6 Correct 20 ms 4568 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 5412 KB Correct.
2 Correct 43 ms 7304 KB Correct.
3 Correct 687 ms 175136 KB Correct.
4 Correct 490 ms 42092 KB Correct.
5 Correct 1055 ms 101908 KB Correct.
6 Correct 437 ms 57392 KB Correct.
7 Correct 482 ms 45972 KB Correct.
8 Correct 468 ms 9160 KB Correct.
9 Correct 195 ms 5996 KB Correct.
10 Correct 183 ms 5432 KB Correct.
11 Correct 507 ms 5160 KB Correct.
12 Correct 219 ms 5420 KB Correct.
13 Correct 233 ms 5448 KB Correct.
14 Correct 436 ms 86964 KB Correct.
15 Correct 451 ms 25648 KB Correct.
16 Correct 211 ms 5420 KB Correct.
17 Correct 268 ms 5344 KB Correct.
18 Correct 222 ms 5384 KB Correct.
19 Correct 526 ms 5340 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 16 ms 4796 KB Correct.
22 Correct 33 ms 6856 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 6508 KB Correct.
2 Correct 96 ms 9336 KB Correct.
3 Correct 580 ms 183432 KB Correct.
4 Correct 763 ms 15320 KB Correct.
5 Correct 2304 ms 134704 KB Correct.
6 Correct 1073 ms 90204 KB Correct.
7 Correct 866 ms 67088 KB Correct.
8 Correct 852 ms 5780 KB Correct.
9 Correct 463 ms 7500 KB Correct.
10 Correct 438 ms 6536 KB Correct.
11 Correct 1089 ms 2912 KB Correct.
12 Correct 576 ms 6536 KB Correct.
13 Correct 571 ms 6616 KB Correct.
14 Correct 2671 ms 121464 KB Correct.
15 Correct 2234 ms 95188 KB Correct.
16 Correct 1407 ms 37108 KB Correct.
17 Correct 993 ms 10680 KB Correct.
18 Correct 472 ms 6380 KB Correct.
19 Correct 615 ms 6552 KB Correct.
20 Correct 548 ms 6444 KB Correct.
21 Correct 1297 ms 6380 KB Correct.
22 Correct 37 ms 3684 KB Correct.
23 Correct 36 ms 5852 KB Correct.
24 Correct 70 ms 8892 KB Correct.