oj.uz

Submission #794548

# Submission time Handle Problem Language Result Execution time Memory
794548 2023-07-26T15:41:45 Z FEDIKUS Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 303132 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,100);
  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 2748 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3636 KB Correct.
2 Correct 21 ms 3632 KB Correct.
3 Correct 20 ms 3680 KB Correct.
4 Correct 21 ms 3664 KB Correct.
5 Correct 21 ms 3656 KB Correct.
6 Correct 22 ms 11844 KB Correct.
7 Correct 27 ms 11604 KB Correct.
8 Correct 19 ms 20888 KB Correct.
9 Correct 20 ms 2824 KB Correct.
10 Correct 20 ms 2816 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3632 KB Correct.
2 Correct 23 ms 3668 KB Correct.
3 Correct 21 ms 3668 KB Correct.
4 Correct 21 ms 2772 KB Correct.
5 Correct 23 ms 2820 KB Correct.
6 Correct 8 ms 10196 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 61172 KB Correct.
2 Correct 270 ms 4928 KB Correct.
3 Correct 230 ms 4932 KB Correct.
4 Correct 249 ms 4964 KB Correct.
5 Correct 200 ms 3744 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3704 KB Correct.
2 Correct 20 ms 3708 KB Correct.
3 Correct 19 ms 3704 KB Correct.
4 Correct 23 ms 11860 KB Correct.
5 Correct 17 ms 2812 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3668 KB Correct.
2 Correct 17 ms 3644 KB Correct.
3 Correct 56 ms 72944 KB Correct.
4 Correct 16 ms 9428 KB Correct.
5 Correct 18 ms 2772 KB Correct.
6 Correct 19 ms 3732 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 4624 KB Correct.
2 Correct 38 ms 6116 KB Correct.
3 Correct 564 ms 95572 KB Correct.
4 Correct 470 ms 25756 KB Correct.
5 Correct 958 ms 73108 KB Correct.
6 Correct 440 ms 49964 KB Correct.
7 Correct 448 ms 26932 KB Correct.
8 Correct 457 ms 7868 KB Correct.
9 Correct 203 ms 5552 KB Correct.
10 Correct 191 ms 5500 KB Correct.
11 Correct 453 ms 5868 KB Correct.
12 Correct 227 ms 5424 KB Correct.
13 Correct 244 ms 5480 KB Correct.
14 Correct 385 ms 49320 KB Correct.
15 Correct 443 ms 16984 KB Correct.
16 Correct 204 ms 5416 KB Correct.
17 Correct 264 ms 5568 KB Correct.
18 Correct 232 ms 5492 KB Correct.
19 Correct 545 ms 6404 KB Correct.
20 Correct 18 ms 3156 KB Correct.
21 Correct 17 ms 4096 KB Correct.
22 Correct 34 ms 6216 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 10060 KB Correct.
2 Correct 187 ms 12368 KB Correct.
3 Correct 814 ms 100768 KB Correct.
4 Correct 1340 ms 13708 KB Correct.
5 Execution timed out 3073 ms 303132 KB Time limit exceeded
6 Halted 0 ms 0 KB -