제출 #954061

#제출 시각아이디문제언어결과실행 시간메모리
954061Otalp사이버랜드 (APIO23_cyberland)C++17
44 / 100
1126 ms107776 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pb push_back #define ff first #define ss second vector<pair<int, int>> q[200100]; double dp[200100][105]; int us[200100][105]; int pos[200100]; int H; void dfs(int v){ pos[v] = 1; if(v == H) return; for(int i=0; i<q[v].size(); i++){ int to = q[v][i].ff; if(pos[to]) continue; dfs(to); } } double st[200]; double solve(int n, int m, int K, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { H = h; int k = min(K, 100); for(int i=0; i<n; i++){ q[i].clear(); for(int j=0; j<=k; j++){ dp[i][j] = us[i][j] = 0; } pos[i] = 0; } for(int i=0; i<m; i++){ q[x[i]].pb({y[i], c[i]}); q[y[i]].pb({x[i], c[i]}); } st[0]= 1; for(int i=1; i<=k + 2; i++){ st[i] = st[i - 1] / 2; } dfs(0); if(pos[h] == 0) return -1; set<pair<pair<int, double>, int>> s; s.insert({{0, 0}, h}); while(s.size()){ auto it = s.begin(); if(us[it -> ss][it -> ff.ff]){ s.erase(it); continue; } int v = it -> ss; int c = it -> ff.ff; us[v][c] = 1; dp[v][c] = it -> ff.ss; for(int i=0; i<q[v].size(); i++){ int to = q[v][i].ff; int x = q[v][i].ss; if(!us[to][c] and to != h){ s.insert({{c, dp[v][c] + x / st[c]}, to}); } if(arr[to] == 2 and c + 1 <= k and !us[to][c+1] and to != h){ s.insert({{c + 1, dp[v][c] + x / st[c]}, to}); } } } double mn=1e18; if(k < K){ for(int i=0; i<n; i++){ if(us[i][k]) mn = min(mn, dp[i][k]); } } arr[0] = 0; for(int i=0; i<n; i++){ if(pos[i] and arr[i] == 0){ for(int j=0; j<=k; j++){ if(us[i][j]) mn = min(mn, dp[i][j]); } } } if(mn == 1e18) return -1; return mn; }

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

cyberland.cpp: In function 'void dfs(int)':
cyberland.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0; i<q[v].size(); i++){
      |                  ~^~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i=0; i<q[v].size(); i++){
      |                      ~^~~~~~~~~~~~
#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...