Submission #1203274

#TimeUsernameProblemLanguageResultExecution timeMemory
1203274Mher777Cyberland (APIO23_cyberland)C++20
15 / 100
3096 ms33460 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <iomanip> #include <array> #include <string> #include <algorithm> #include <cmath> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <utility> #include <random> #include <cassert> #include <fstream> #include "cyberland.h" using namespace std; mt19937 rnd(7069); typedef int itn; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef float fl; typedef long double ld; using vi = vector<int>; using vll = vector<ll>; using mii = map<int, int>; using mll = map<ll, ll>; using pii = pair<int, int>; using pll = pair<ll, ll>; #define ff first #define ss second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define mpr make_pair #define yes cout<<"Yes\n" #define no cout<<"No\n" #define all(x) (x).begin(), (x).end() #define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout); const double MAX = 1000000000000000000; const ll MOD = ll(1000000007); const ll MOD2 = ll(998244353); const int max_N = 100005, max_M = 35; int type[max_N], used[max_N]; db dist[max_N][max_M]; vector<pair<int, db>> g[max_N]; int n, m, k; priority_queue<pair<pair<db, int>, int>> pq; void clr() { while (!pq.empty()) { pq.pop(); } for (int i = 0; i < n; ++i) { used[i] = 0; g[i].clear(); for (int j = 0; j <= k; ++j) { dist[i][j] = MAX; } } } void dfs(int u = 0) { used[u] = 1; if (!type[u]) { pq.push({ {0,0},u }); dist[u][0] = 0; } for (auto opt : g[u]) { int to = opt.ff; if (used[to]) continue; dfs(to); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { n = N, m = M, k = K; for (int i = 0; i < m; ++i) { g[x[i]].pub({ y[i],(db)c[i] }); g[y[i]].pub({ x[i],(db)c[i] }); } for (int i = 0; i < n; ++i) { type[i] = arr[i]; for (int j = 0; j <= k; ++j) { dist[i][j] = MAX; } } pq.push({ {0,0},0 }); dist[0][0] = 0; dfs(); if (!used[H]) { clr(); return -1; } while (!pq.empty()) { db her = pq.top().ff.ff; int k_u = pq.top().ff.ss; int u = pq.top().ss; pq.pop(); if (her > dist[u][k_u]) continue; for (auto opt : g[u]) { int to = opt.ff; db w = opt.ss; if (!type[to]) continue; if (dist[to][k_u] > dist[u][k_u] + w) { dist[to][k_u] = dist[u][k_u] + w; pq.push({ {-dist[to][k_u],k_u},to }); } if (type[to] == 2 && k_u != k && dist[to][k_u + 1] > dist[u][k_u] / (db)2 + w) { dist[to][k_u + 1] = dist[u][k_u] / (db)2 + w; pq.push({ {-dist[to][k_u + 1],k_u + 1},to }); } } } db ans = MAX; for (int j = 0; j <= k; ++j) { ans = min(ans, dist[H][j]); } clr(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...