oj.uz

Submission #794551

# Submission time Handle Problem Language Result Execution time Memory
794551 2023-07-26T15:42:31 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 170028 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 17 ms 2900 KB Correct.
2 Correct 22 ms 3036 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4032 KB Correct.
2 Correct 25 ms 4572 KB Correct.
3 Correct 22 ms 4504 KB Correct.
4 Correct 22 ms 4552 KB Correct.
5 Correct 23 ms 4480 KB Correct.
6 Correct 24 ms 12632 KB Correct.
7 Correct 30 ms 12536 KB Correct.
8 Correct 18 ms 21236 KB Correct.
9 Correct 21 ms 3552 KB Correct.
10 Correct 24 ms 3536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4472 KB Correct.
2 Correct 30 ms 4424 KB Correct.
3 Correct 22 ms 4532 KB Correct.
4 Correct 23 ms 3080 KB Correct.
5 Correct 30 ms 3616 KB Correct.
6 Correct 12 ms 10456 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 62172 KB Correct.
2 Correct 270 ms 4016 KB Correct.
3 Correct 231 ms 4056 KB Correct.
4 Correct 248 ms 4092 KB Correct.
5 Correct 201 ms 2868 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4468 KB Correct.
2 Correct 30 ms 4524 KB Correct.
3 Correct 20 ms 4556 KB Correct.
4 Correct 23 ms 12840 KB Correct.
5 Correct 19 ms 3516 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4540 KB Correct.
2 Correct 26 ms 4444 KB Correct.
3 Correct 53 ms 74304 KB Correct.
4 Correct 16 ms 9924 KB Correct.
5 Correct 19 ms 3668 KB Correct.
6 Correct 23 ms 4252 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 5368 KB Correct.
2 Correct 37 ms 6012 KB Correct.
3 Correct 607 ms 93332 KB Correct.
4 Correct 495 ms 23592 KB Correct.
5 Correct 1045 ms 71512 KB Correct.
6 Correct 467 ms 48696 KB Correct.
7 Correct 447 ms 25560 KB Correct.
8 Correct 454 ms 6184 KB Correct.
9 Correct 203 ms 5160 KB Correct.
10 Correct 192 ms 4960 KB Correct.
11 Correct 451 ms 4136 KB Correct.
12 Correct 227 ms 4704 KB Correct.
13 Correct 249 ms 4720 KB Correct.
14 Correct 389 ms 47204 KB Correct.
15 Correct 440 ms 15024 KB Correct.
16 Correct 206 ms 4536 KB Correct.
17 Correct 264 ms 4604 KB Correct.
18 Correct 230 ms 4564 KB Correct.
19 Correct 545 ms 4628 KB Correct.
20 Correct 17 ms 3156 KB Correct.
21 Correct 16 ms 4036 KB Correct.
22 Correct 32 ms 6088 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 8136 KB Correct.
2 Correct 135 ms 11184 KB Correct.
3 Correct 608 ms 98292 KB Correct.
4 Correct 1058 ms 10468 KB Correct.
5 Execution timed out 3059 ms 170028 KB Time limit exceeded
6 Halted 0 ms 0 KB -