Submission #969132

#	Time	Username	Problem	Language	Result	Execution time	Memory
969132		Br3ad	Cyberland (APIO23_cyberland)	C++17	8 / 100	3056 ms	2097152 KiB

cyberland

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
#define ll long long
#define f first
#define s second
#define PB push_back
#define MP make_pair
#define min(a, b) ((a < b)? a : b)

const int N = 1e5 + 5;
const int M = 1e9 + 7;
const long double INF = 1e14;

vector<vector<pair<int, int>>> adj(N);
bool vis[N]{false};

void init(int n){
  for(int i = 0; i < n; i++) adj[i].clear();
  memset(vis, false, sizeof(vis));
}

long double DFS(int v, int target, long double time, vector<int> arr){
  // cout << v << ' ' << time << endl;
  vis[v] = true;  
  if(v == target) return time;
  // if(vis[v]) return INF;

  long double mn = INF;
  for(auto i : adj[v]){
    if(vis[i.f]) continue;
    long double temp;
    if(arr[i.f] == 0){
      temp = DFS(i.f, target, 0, arr);
    }else if(arr[i.f] == 2){
      temp = DFS(i.f, target, (long double)(time + i.s)/2, arr);
    }else {
      temp = DFS(i.f, target, time + i.s, arr);
    }
    mn = min(mn, temp);
    // cout << mn << endl;
  }
  vis[v] = false;
  
  return mn;
}

// Subtask 1~6 (Greedy)
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
  init(n);
  for(int i = 0; i < m; i++){
    adj[x[i]].PB(MP(y[i], c[i]));
    adj[y[i]].PB(MP(x[i], c[i]));
  }
  
  long double ans = DFS(0, h, 0, arr);
  if(vis[h]){
    return ans;
  }else {
    return -1;
  }
}

// int main(){
//   // Driver Code
//   cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
//   cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
// }

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