Submission #1197527

#TimeUsernameProblemLanguageResultExecution timeMemory
1197527b00legen사이버랜드 (APIO23_cyberland)C++17
44 / 100
3096 ms2162688 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; double solve(int n, int m, int k, int h, vector<int>x, vector<int>y, vector<int>c, vector<int>arr) { vector<pair<int, double> >g[n]; for (int i = 0; i < m; i++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } vector<int>bg; { int vis[n]; vis[1] = 2; for (int i = 1; i < n; i++) vis[i] = 0; queue<int>q; q.push(0); while (!q.empty()) { int v = q.front(); q.pop(); if (arr[v] == 0 || v == 0) { bg.push_back(v); vis[v] = 2; } for (size_t i = 0; i < g[v].size(); i++) { int to = g[v][i].first; if (to != h && !vis[to]) { q.push(to); vis[to] = 1; } } } vis[h] = 1; vector<pair<int, double> >g2[n]; for (int v = 0; v < n; v++) { if (!vis[v]) continue; for (size_t i = 0; i < g[v].size(); i++) { int to = g[v][i].first; if (vis[to] == 1) g2[v].push_back(g[v][i]); } } for (int i = 0; i < n; i++) g[i] = g2[i]; } pair<double, int>d[n]; for (int i = 0; i < n; i++) d[i] = {1e15, 0}; queue<pair<pair<double, int>, int>>q; for (size_t i = 0; i < bg.size(); i++) q.push({{0, k}, bg[i]}); while (!q.empty()) { pair<double, int>vl = q.front().first; int v = q.front().second; q.pop(); if (vl.first < d[v].first || vl.second > d[v].second) { d[v] = vl; for (size_t i = 0; i < g[v].size(); i++) { int to = g[v][i].first; q.push({{vl.first + g[v][i].second, vl.second}, to}); if (arr[to] == 2 && vl.second) q.push({{(vl.first + g[v][i].second) / 2, vl.second - 1}, to}); } } } if (d[h].first == 1e15) return -1; else return d[h].first; }
#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...