Submission #982390

#TimeUsernameProblemLanguageResultExecution timeMemory
982390Alkaser_IDCyberland (APIO23_cyberland)C++17
97 / 100
3052 ms74300 KiB
#include "cyberland.h" using namespace std; #include <bits/stdc++.h> typedef long double db; typedef long long ll; ll n,m,tar,kK=0; int ab[100005]; db res = -1; vector<pair<int,db>> adj[100005]; db dis[100005][33]; inline void bfs(int i,int k){ vector<pair<int,int>> bs; for(int j=0;j<adj[i].size();++j){ if(adj[i][j].first == tar) { res = min(res,dis[i][k] + adj[i][j].second); } else{ ll nx = adj[i][j].first;db vl = adj[i][j].second,cr = dis[i][k]; if(ab[nx] == 0 && dis[nx][k] > 0){ dis[nx][k] = 0; bs.push_back({nx,k}); } if(cr + vl < dis[nx][k]) { dis[nx][k] = cr + vl; bs.push_back({nx,k}); } if(ab[nx] == 2 && k < kK){ if(((cr + vl) / 2) < dis[nx][k+1]){ dis[nx][k+1] = (cr + vl) / 2; bs.push_back({nx,k+1}); } } } } for(int j=0;j<bs.size();++j){ bfs(bs[j].first,bs[j].second); } } 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; tar = H; kK = K; for(int i=0;i<n;++i) ab[i] = arr[i]; for(int i=0;i<=n;++i) adj[i].clear(); res = 1e15; for(int i=0;i<m;++i) { adj[x[i]].push_back({y[i],c[i]}); adj[y[i]].push_back({x[i],c[i]}); } for(ll i=0;i<n;++i){ for(ll j=0;j<=K;++j) dis[i][j] = 1e15; } dis[0][0] = 0; bfs(0,0); if(res == 1e15) return -1; return res; } /* 1 3 2 30 2 1 2 1 1 2 12 2 0 4 1 4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4 */

Compilation message (stderr)

cyberland.cpp: In function 'void bfs(int, int)':
cyberland.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int j=0;j<adj[i].size();++j){
      |                 ~^~~~~~~~~~~~~~
cyberland.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=0;j<bs.size();++j){
      |                 ~^~~~~~~~~~
#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...