Submission #976237

#	Time	Username	Problem	Language	Result	Execution time	Memory
976237		Tsagana	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 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

using namespace std;

// START

struct country
{
  double cost[31];
};

country cnt[100001];
vector<pi> adj[100001];
vi ar;
int h, D;

int vs[100001];
vi takes(int s) {
  vi v;
  pq<int> q;
  q.push(s);
  while (!q.empty()) {
    s = q.top(); q.pop();
    for (auto i: adj[s]) {
      if (vs[i.S]) continue ;
      vs[i.S] = 1;
      if (!ar[i.S]) v.pb(i.S); 
      q.push(i.S);
    }
  }
  return v;
}
void dfs(int s, int k, double cos)
{
  if (k > D) return ;
  if (cnt[s].cost[k] <= cos) return ;
  cnt[s].cost[k] = cos;

  // cout << s << ' ' << k << ' ';
  // printf("%.12lf\n", cos);
  if (s == h) return ;
  for (auto i: adj[s]) {
    double c = i.F;
    int x = i.S;

    dfs(x, k, c + cos);
    if (ar[s] == 2 && k <= D) dfs(x, k + 1, c + (cos / 2.0));
  }
}
double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
  ar = arr;
  h = H; D = K;
  for (int i = 0; i < M; i++) {
    adj[x[i]].pb({c[i], y[i]});
    adj[y[i]].pb({c[i], x[i]});
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      cnt[i].cost[j] = 1e9;
    }
  }
  vi v = takes(0);
  for (auto i: v) {
    adj[0].pb({0, i});
  }
  dfs(0, 0, 0.0);

  double ans = cnt[H].cost[0];
  for (int i = 1; i <= K; i++) {
   if (ans > cnt[H].cost[i]) ans = cnt[H].cost[i];
  }
  return ans;
}

//END

int32 main() {
  int T;
  assert(1 == scanf("%lld", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%lld %lld %lld\n%lld", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%lld", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%lld %lld %lld", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}

Compilation message (stderr)

cyberland.cpp:92:1: error: 'int32' does not name a type; did you mean 'int32_t'?
   92 | int32 main() {
      | ^~~~~
      | int32_t