제출 #975242

#제출 시각아이디문제언어결과실행 시간메모리
975242ShaShi사이버랜드 (APIO23_cyberland)C++17
0 / 100
58 ms66760 KiB
#include <bits/stdc++.h> #include "cyberland.h" #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define mp make_pair #define F first #define S second using namespace std; typedef long long ll; const int MAXN = (int)1e6 + 7; const int K = 70; const int MOD = 998244353; const double INF = (double)1e18 + 7; int n, m, k, h, tmp, tmp2, tmp3, tmp4, ans, u, v, w; int arr[MAXN]; double dp[MAXN][K], p2[K]; bool seen[MAXN], sn[MAXN][K]; vector<pii> adj[MAXN]; priority_queue<pair<double, pii>, vector<pair<double, pii> >, greater<pair<double, pii> > > pq; void DFS(int v) { seen[v] = 1; for (auto cur:adj[v]) { int u = cur.F, w = cur.S; if (!seen[u]) DFS(u); } } inline void relax(int v, int x, int d) { if (dp[v][x] > d) { dp[v][x] = d; pq.push(mp(d, mp(v, x))); } } double solve(int N, int M, int kk, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> A) { n = N; m = M; k = min(K-1, kk); h = H; for (int i=0; i<n; i++) adj[i].clear(); fill(seen, seen+n+1, 0); p2[0] = 1.0; for (int i=1; i<K; i++) p2[i] = p2[i-1]/2.0; for (int j=0; j<K; j++) for (int i=0; i<n; i++) dp[i][j] = INF; for (int i=0; i<m; i++) { u = x[i]; v = y[i]; w = c[i]; adj[u].pb(mp(v, w)); adj[v].pb(mp(u, w)); } for (int i=0; i<n; i++) arr[i] = A[i]; DFS(0); if (!seen[h]) return -1; relax(h, k, 0); while (pq.size()) { auto cur = pq.top(); pq.pop(); v = cur.S.F; tmp = cur.S.S; if (dp[v][tmp] < cur.F) continue; if (arr[v] == 0 || v == 0) return cur.F; for (auto cur:adj[v]) { int u = cur.F, w = cur.S; relax(u, tmp, dp[v][tmp] + w*p2[k-tmp]); if (arr[v] == 2 && k > 0) relax(u, tmp-1, dp[v][tmp]+w*p2[k-tmp+1]); } } return -1; }

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In function 'void DFS(int)':
cyberland.cpp:35:24: warning: unused variable 'w' [-Wunused-variable]
   35 |         int u = cur.F, w = cur.S;
      |                        ^
#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...