# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
990013 | 2024-05-29T11:13:09 Z | Mihailo | 사이버랜드 (APIO23_cyberland) | C++17 | 981 ms | 22416 KB |
#include "cyberland.h" #include <cassert> #include <cstdio> #include <bits/stdc++.h> #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define xx first #define yy second using namespace std; typedef long long ll; vector<pair<__int128, long double> > adj[100100], v; int a[100100], n, ks; long double dis[100100], rez; void dikstra() { priority_queue<pair<__int128, __int128> > q; pair<__int128, __int128> cur; for(int i=0; i<=n; i++) dis[i]=-1; // cout<<'\n'; for(int j=0; j<v.size(); j++) { for(int i=0; i<adj[v[j].xx].size(); i++) { if(dis[adj[v[j].xx][i].xx]==-1) q.push(mp(v[j].yy-adj[v[j].xx][i].yy, adj[v[j].xx][i].xx)); } } while(q.size()) { cur=q.top(); q.pop(); // cout<<cur.xx<<' '<<cur.yy<<'\n'; if(dis[cur.yy]!=-1) continue; dis[cur.yy]=-cur.xx; for(int i=0; i<adj[cur.yy].size(); i++) { if(dis[adj[cur.yy][i].xx]==-1) q.push(mp(cur.xx-adj[cur.yy][i].yy, adj[cur.yy][i].xx)); } } } 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) { K=min(100, K); for(int i=0; i<=N; i++) adj[i].clear(); for(int i=0; i<M; i++) { adj[x[i]+1].pb(mp(y[i]+1, c[i])); adj[y[i]+1].pb(mp(x[i]+1, c[i])); } adj[H+1].clear(); n=N; a[0]=1; a[1]=0; for(int i=1; i<arr.size(); i++) { a[i+1]=arr[i]; } ///////// adj[0].pb(mp(1, 0)); v.clear(); v.push_back(mp(0, 0)); dikstra(); if(dis[H+1]==-1) return -1; for(int i=1; i<=n; i++) { if(dis[i]==-1) a[i]=1; } adj[0].clear(); ///////// for(int i=1; i<=N; i++) { if(a[i]==0) adj[0].pb(mp(i, 0)); } rez=1e30; ks=K; K++; while(K--) { dikstra(); if(dis[H+1]>=0) rez=min(rez, dis[H+1]*(ll)pow(2, K)); v.clear(); for(int i=1; i<=N; i++) { if(a[i]==2) v.pb(mp(i, -dis[i])); } for(int i=0; i<=N; i++) { for(int j=0; j<adj[i].size(); j++) adj[i][j].yy*=2; } } return rez/((long double)pow(2, ks)); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 4952 KB | Correct. |
2 | Correct | 24 ms | 4700 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 4700 KB | Correct. |
2 | Correct | 38 ms | 4808 KB | Correct. |
3 | Correct | 37 ms | 4700 KB | Correct. |
4 | Correct | 38 ms | 4756 KB | Correct. |
5 | Correct | 39 ms | 4700 KB | Correct. |
6 | Correct | 36 ms | 6232 KB | Correct. |
7 | Correct | 47 ms | 6136 KB | Correct. |
8 | Correct | 24 ms | 7256 KB | Correct. |
9 | Correct | 35 ms | 4444 KB | Correct. |
10 | Correct | 37 ms | 4664 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 4696 KB | Correct. |
2 | Correct | 44 ms | 4948 KB | Correct. |
3 | Correct | 41 ms | 4956 KB | Correct. |
4 | Correct | 42 ms | 4656 KB | Correct. |
5 | Correct | 42 ms | 4444 KB | Correct. |
6 | Correct | 10 ms | 6104 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 170 ms | 12264 KB | Correct. |
2 | Correct | 185 ms | 4824 KB | Correct. |
3 | Correct | 158 ms | 4696 KB | Correct. |
4 | Correct | 181 ms | 4700 KB | Correct. |
5 | Correct | 134 ms | 4440 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 4952 KB | Correct. |
2 | Correct | 31 ms | 4956 KB | Correct. |
3 | Correct | 31 ms | 5080 KB | Correct. |
4 | Correct | 39 ms | 7324 KB | Correct. |
5 | Correct | 25 ms | 4440 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 4952 KB | Correct. |
2 | Correct | 30 ms | 4952 KB | Correct. |
3 | Correct | 30 ms | 14164 KB | Correct. |
4 | Correct | 25 ms | 6736 KB | Correct. |
5 | Correct | 31 ms | 4696 KB | Correct. |
6 | Correct | 35 ms | 4956 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 269 ms | 4948 KB | Correct. |
2 | Correct | 50 ms | 5204 KB | Correct. |
3 | Correct | 412 ms | 16440 KB | Correct. |
4 | Correct | 313 ms | 8016 KB | Correct. |
5 | Correct | 981 ms | 22416 KB | Correct. |
6 | Correct | 862 ms | 21944 KB | Correct. |
7 | Correct | 323 ms | 8128 KB | Correct. |
8 | Correct | 263 ms | 5204 KB | Correct. |
9 | Correct | 221 ms | 4948 KB | Correct. |
10 | Correct | 200 ms | 5204 KB | Correct. |
11 | Correct | 253 ms | 4944 KB | Correct. |
12 | Correct | 242 ms | 4948 KB | Correct. |
13 | Correct | 252 ms | 4960 KB | Correct. |
14 | Correct | 303 ms | 11036 KB | Correct. |
15 | Correct | 301 ms | 6648 KB | Correct. |
16 | Correct | 230 ms | 5192 KB | Correct. |
17 | Correct | 266 ms | 4976 KB | Correct. |
18 | Correct | 244 ms | 4956 KB | Correct. |
19 | Correct | 466 ms | 4912 KB | Correct. |
20 | Correct | 14 ms | 4444 KB | Correct. |
21 | Correct | 15 ms | 4840 KB | Correct. |
22 | Correct | 84 ms | 6628 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 778 ms | 5112 KB | Double -1.56918e+09 violates the range [-1, 1e+18] |
2 | Halted | 0 ms | 0 KB | - |