# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
990014 | 2024-05-29T11:14:07 Z | Mihailo | 사이버랜드 (APIO23_cyberland) | C++17 | 957 ms | 22848 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(30, 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 | 4696 KB | Correct. |
2 | Correct | 29 ms | 4700 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 4856 KB | Correct. |
2 | Correct | 39 ms | 4696 KB | Correct. |
3 | Correct | 37 ms | 4848 KB | Correct. |
4 | Correct | 38 ms | 4700 KB | Correct. |
5 | Correct | 38 ms | 4848 KB | Correct. |
6 | Correct | 44 ms | 6212 KB | Correct. |
7 | Correct | 46 ms | 5980 KB | Correct. |
8 | Correct | 21 ms | 7256 KB | Correct. |
9 | Correct | 35 ms | 4656 KB | Correct. |
10 | Correct | 35 ms | 4444 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 4796 KB | Correct. |
2 | Correct | 45 ms | 4700 KB | Correct. |
3 | Correct | 41 ms | 4952 KB | Correct. |
4 | Correct | 48 ms | 4672 KB | Correct. |
5 | Correct | 46 ms | 4440 KB | Correct. |
6 | Correct | 10 ms | 6104 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 169 ms | 12120 KB | Correct. |
2 | Correct | 182 ms | 4700 KB | Correct. |
3 | Correct | 162 ms | 4760 KB | Correct. |
4 | Correct | 172 ms | 4696 KB | Correct. |
5 | Correct | 141 ms | 4440 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 4952 KB | Correct. |
2 | Correct | 31 ms | 4952 KB | Correct. |
3 | Correct | 31 ms | 5084 KB | Correct. |
4 | Correct | 39 ms | 7460 KB | Correct. |
5 | Correct | 24 ms | 4696 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 5100 KB | Correct. |
2 | Correct | 29 ms | 4952 KB | Correct. |
3 | Correct | 33 ms | 14172 KB | Correct. |
4 | Correct | 27 ms | 6768 KB | Correct. |
5 | Correct | 31 ms | 4444 KB | Correct. |
6 | Correct | 36 ms | 4956 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 262 ms | 4936 KB | Correct. |
2 | Correct | 51 ms | 5212 KB | Correct. |
3 | Correct | 407 ms | 16464 KB | Correct. |
4 | Correct | 312 ms | 8020 KB | Correct. |
5 | Correct | 957 ms | 22848 KB | Correct. |
6 | Correct | 852 ms | 21732 KB | Correct. |
7 | Correct | 317 ms | 7764 KB | Correct. |
8 | Correct | 263 ms | 5200 KB | Correct. |
9 | Correct | 230 ms | 5204 KB | Correct. |
10 | Correct | 199 ms | 5200 KB | Correct. |
11 | Correct | 254 ms | 4968 KB | Correct. |
12 | Correct | 237 ms | 4948 KB | Correct. |
13 | Correct | 249 ms | 5200 KB | Correct. |
14 | Correct | 307 ms | 11040 KB | Correct. |
15 | Correct | 295 ms | 6480 KB | Correct. |
16 | Correct | 239 ms | 5052 KB | Correct. |
17 | Correct | 273 ms | 4956 KB | Correct. |
18 | Correct | 242 ms | 4956 KB | Correct. |
19 | Correct | 499 ms | 4948 KB | Correct. |
20 | Correct | 14 ms | 4444 KB | Correct. |
21 | Correct | 15 ms | 4784 KB | Correct. |
22 | Correct | 83 ms | 6696 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 256 ms | 4948 KB | Correct. |
2 | Correct | 50 ms | 5208 KB | Correct. |
3 | Incorrect | 271 ms | 18000 KB | Wrong Answer. |
4 | Halted | 0 ms | 0 KB | - |