oj.uz

Submission #794556

# Submission time Handle Problem Language Result Execution time Memory
794556 2023-07-26T15:45:42 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 169800 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,68);
  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 15 ms 2772 KB Correct.
2 Correct 15 ms 2808 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3668 KB Correct.
2 Correct 22 ms 3660 KB Correct.
3 Correct 21 ms 3644 KB Correct.
4 Correct 21 ms 3668 KB Correct.
5 Correct 21 ms 3668 KB Correct.
6 Correct 23 ms 11860 KB Correct.
7 Correct 28 ms 11564 KB Correct.
8 Correct 19 ms 20948 KB Correct.
9 Correct 19 ms 2824 KB Correct.
10 Correct 19 ms 2816 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3640 KB Correct.
2 Correct 22 ms 3684 KB Correct.
3 Correct 21 ms 3672 KB Correct.
4 Correct 21 ms 2820 KB Correct.
5 Correct 21 ms 2812 KB Correct.
6 Correct 8 ms 10196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 61040 KB Correct.
2 Correct 267 ms 4044 KB Correct.
3 Correct 236 ms 4220 KB Correct.
4 Correct 250 ms 4024 KB Correct.
5 Correct 202 ms 2852 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3668 KB Correct.
2 Correct 23 ms 3632 KB Correct.
3 Correct 20 ms 3692 KB Correct.
4 Correct 24 ms 11896 KB Correct.
5 Correct 17 ms 2812 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3668 KB Correct.
2 Correct 17 ms 3604 KB Correct.
3 Correct 56 ms 72956 KB Correct.
4 Correct 18 ms 9300 KB Correct.
5 Correct 19 ms 2828 KB Correct.
6 Correct 19 ms 3668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 4588 KB Correct.
2 Correct 39 ms 5996 KB Correct.
3 Correct 610 ms 93284 KB Correct.
4 Correct 474 ms 23612 KB Correct.
5 Correct 997 ms 71412 KB Correct.
6 Correct 517 ms 48692 KB Correct.
7 Correct 468 ms 25548 KB Correct.
8 Correct 456 ms 6176 KB Correct.
9 Correct 202 ms 5128 KB Correct.
10 Correct 191 ms 4624 KB Correct.
11 Correct 483 ms 4112 KB Correct.
12 Correct 229 ms 4600 KB Correct.
13 Correct 244 ms 4636 KB Correct.
14 Correct 387 ms 47220 KB Correct.
15 Correct 441 ms 14980 KB Correct.
16 Correct 207 ms 4540 KB Correct.
17 Correct 265 ms 4556 KB Correct.
18 Correct 231 ms 4508 KB Correct.
19 Correct 547 ms 4528 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 16 ms 4000 KB Correct.
22 Correct 32 ms 6088 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 7304 KB Correct.
2 Correct 119 ms 10460 KB Correct.
3 Correct 554 ms 97344 KB Correct.
4 Correct 1026 ms 10328 KB Correct.
5 Execution timed out 3055 ms 169800 KB Time limit exceeded
6 Halted 0 ms 0 KB -