# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
990015 | 2024-05-29T11:15:12 Z | Mihailo | 사이버랜드 (APIO23_cyberland) | C++17 | 1000 ms | 23508 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(50, 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 | 24 ms | 4696 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 4696 KB | Correct. |
2 | Correct | 39 ms | 4824 KB | Correct. |
3 | Correct | 37 ms | 4700 KB | Correct. |
4 | Correct | 38 ms | 4700 KB | Correct. |
5 | Correct | 38 ms | 4700 KB | Correct. |
6 | Correct | 36 ms | 6228 KB | Correct. |
7 | Correct | 48 ms | 5976 KB | Correct. |
8 | Correct | 22 ms | 7260 KB | Correct. |
9 | Correct | 35 ms | 4444 KB | Correct. |
10 | Correct | 39 ms | 4700 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 4896 KB | Correct. |
2 | Correct | 44 ms | 4944 KB | Correct. |
3 | Correct | 41 ms | 4948 KB | Correct. |
4 | Correct | 43 ms | 4440 KB | Correct. |
5 | Correct | 42 ms | 4656 KB | Correct. |
6 | Correct | 10 ms | 6100 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 172 ms | 12120 KB | Correct. |
2 | Correct | 186 ms | 4696 KB | Correct. |
3 | Correct | 166 ms | 4696 KB | Correct. |
4 | Correct | 172 ms | 4700 KB | Correct. |
5 | Correct | 135 ms | 4444 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 4952 KB | Correct. |
2 | Correct | 31 ms | 5076 KB | Correct. |
3 | Correct | 31 ms | 5048 KB | Correct. |
4 | Correct | 41 ms | 7352 KB | Correct. |
5 | Correct | 24 ms | 4440 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 4956 KB | Correct. |
2 | Correct | 31 ms | 4956 KB | Correct. |
3 | Correct | 30 ms | 14164 KB | Correct. |
4 | Correct | 25 ms | 6704 KB | Correct. |
5 | Correct | 31 ms | 4444 KB | Correct. |
6 | Correct | 35 ms | 4956 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 295 ms | 4944 KB | Correct. |
2 | Correct | 49 ms | 5204 KB | Correct. |
3 | Correct | 409 ms | 16568 KB | Correct. |
4 | Correct | 307 ms | 8016 KB | Correct. |
5 | Correct | 1000 ms | 23508 KB | Correct. |
6 | Correct | 860 ms | 22324 KB | Correct. |
7 | Correct | 316 ms | 7940 KB | Correct. |
8 | Correct | 269 ms | 5372 KB | Correct. |
9 | Correct | 224 ms | 4944 KB | Correct. |
10 | Correct | 202 ms | 5200 KB | Correct. |
11 | Correct | 257 ms | 4944 KB | Correct. |
12 | Correct | 234 ms | 4944 KB | Correct. |
13 | Correct | 260 ms | 5096 KB | Correct. |
14 | Correct | 305 ms | 11052 KB | Correct. |
15 | Correct | 296 ms | 6480 KB | Correct. |
16 | Correct | 236 ms | 5244 KB | Correct. |
17 | Correct | 265 ms | 5200 KB | Correct. |
18 | Correct | 241 ms | 4940 KB | Correct. |
19 | Correct | 498 ms | 4948 KB | Correct. |
20 | Correct | 14 ms | 4440 KB | Correct. |
21 | Correct | 15 ms | 4696 KB | Correct. |
22 | Correct | 84 ms | 6616 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 435 ms | 5144 KB | Correct. |
2 | Correct | 83 ms | 5204 KB | Correct. |
3 | Incorrect | 421 ms | 15704 KB | Wrong Answer. |
4 | Halted | 0 ms | 0 KB | - |