Submission #1203260

#TimeUsernameProblemLanguageResultExecution timeMemory
1203260al95ireyizCyberland (APIO23_cyberland)C++20
97 / 100
850 ms62300 KiB
//*** Bismillah ***// #pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define er erase #define sc second #define in insert #define ll int #define pb push_back #define vll vector<ll> #define pll pair<ll,ll> #define vpll vector<pll> #define len(x)(ll)x.size() #define all(x)x.begin(),x.end() const ll INF = 1e9; const ll INFL = 1e18; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll maxn = 1e5+5; #include "cyberland.h" ll n,m,k=0; ll d; vector<pair<ll, double>> g[maxn]; double dis[maxn][66]; // node, nece defe islenib -> min yol double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a){ n = N, m = M, k = K, d = H + 1; k = min(k, 65); for(ll i = 0; i <= n; i ++){ for(ll j = 0; j <= k; j ++){ dis[i][j] = 1e15; } g[i].clear(); } for(ll i = 0; i < m; i ++){ g[x[i] + 1].pb({y[i] + 1, c[i]}); g[y[i] + 1].pb({x[i] + 1, c[i]}); } priority_queue<pair<double, pll>>q; // w, # of use, u q.push({0, {0, 1}}); dis[1][0] = 0; while(!q.empty()){ ll tmpp = q.top().fr, tm = q.top().sc.fr, u = q.top().sc.sc; q.pop(); if(dis[u][tm] < -tmpp or u == d) continue; for(auto [v, w] : g[u]){ if(a[u - 1] == 0){ if(dis[v][0] > w){ dis[v][0] = w; q.push({-dis[v][0], {0, v}}); } } else{ if(dis[v][tm] > dis[u][tm] + w){ dis[v][tm] = dis[u][tm] + w; q.push({-dis[v][tm], {tm, v}}); } } if(a[u - 1] == 2 and tm < k){ if(dis[v][tm + 1] > dis[u][tm] / 2 + w){ dis[v][tm + 1] = dis[u][tm] / 2 + w; q.push({-dis[v][tm + 1], {tm + 1, v}}); } } } } double cv = 1e15; for(ll i = 0; i <= k; i ++){ cv = min(cv, dis[d][i]); d(dis[d][i]); } return cv == 1e15 ? -1 : cv; } // void _(ll tt){ // } // signed main(){ // ll tm=clock(); // cin.tie(0)->sync_with_stdio(0); // ll t=1; // // cin>>t; // for(ll tt=1;tt<=t;tt++){ // _(tt); // } // cerr<<"\n\033[1;31mTime: \033[1;30m" \ // <<(double)(clock()-tm)/1000000<<"\033[1;32m seconds\n"; // }

Compilation message (stderr)

cyberland.cpp:22:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const ll INFL = 1e18;
      |                 ^~~~
#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...