Submission #976986

#	Time	Username	Problem	Language	Result	Execution time	Memory
976986		Tsagana	Cyberland (APIO23_cyberland)	C++17	49 / 100	1010 ms	19744 KiB

cyberland

#include "cyberland.h"
 
#include <bits/stdc++.h>
 
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
//#define int long long
#define vi vector<int>
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define pid pair<int, double>
#define pdi pair<double, int>
 
using namespace std;
 
// START
vector<pid> adj[100001];
double mindis[100001];
bool reach[100001];
int h, n;

void dfs(int s) {
  reach[s] = 1;
  if (s == h) return ;
  for (auto i: adj[s])
    if (!reach[i.F]) dfs(i.F);
}
void dij(vector<int>& arr) {
  pq<pdi> q;
  for (int i = 0; i < n; i++)
    if (reach[i] && mindis[i] < 1e18) q.push({-mindis[i], i});

  vector<bool> vis(n, 0);
  while (!q.empty()) {
    int s = q.top().S; q.pop();
    if (vis[s]) continue ;
    vis[s] = 1;
    if (s == h) continue ;
    for (auto i: adj[s]) {
      if (reach[i.F] && !vis[i.F] && mindis[i.F] > mindis[s] + i.S) {
        mindis[i.F] = mindis[s] + i.S;
        q.push({mindis[i.F], i.F});
      }
    }
  }
  vector<pid> temp;
  for (int s = 0; s < n; s++) {
    double mn = mindis[s];
    if (reach[s] && arr[s] == 2)
      for (auto i: adj[s])
        if (reach[i.F] && i.F != h) mn = min(mn, (mindis[i.F] + i.S) / 2.0);
    if (mn < mindis[s]) temp.pb({s, mn});
  }
  for (auto i: temp) mindis[i.F] = min(mindis[i.F], i.S);
}
double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
  h = H; n = N;
  K = min(K, 70);
  for (int i = 0; i < N; i++) {
    adj[i].clear();
    reach[i] = 0;
    mindis[i] = 1e18;
  }

  for (int i = 0; i < M; i++) {
    adj[x[i]].pb({y[i], (double)c[i]});
    adj[y[i]].pb({x[i], (double)c[i]});
  }
  dfs(0);
  if (!reach[H]) return -1;

  mindis[0] = 0;
  for (int i = 1; i < N; i++)
    if (reach[i] && arr[i] == 0) mindis[i] = 0;
  
  for (int i = 0; i <= K+1; i++) dij(arr);
  return mindis[H];
}
//END

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3