# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
777192 | 2023-07-08T18:54:38 Z | groshi | Cyberland (APIO23_cyberland) | C++17 | 3000 ms | 237888 KB |
#include<bits/stdc++.h> #include "cyberland.h" using namespace std; struct wi{ vector<int> Q; double dp[203]; int co; int odw=0; }*w; vector<int> moge; void dfs(int x,int nie) { w[x].odw=1; if(x==nie) return; if(w[x].co==0) moge.push_back(x); for(int i=0;i<w[x].Q.size();i+=2) if(w[w[x].Q[i]].odw==0) dfs(w[x].Q[i],nie); } double solve(int32_t n,int32_t m,int32_t k,int32_t h,vector<int32_t> x,vector<int32_t> y,vector<int32_t> c, vector<int32_t> arr) { w=new wi[n+3]; for(int i=0;i<m;i++) { w[x[i]].Q.push_back(y[i]); w[y[i]].Q.push_back(x[i]); w[x[i]].Q.push_back(c[i]); w[y[i]].Q.push_back(c[i]); } for(int i=0;i<n;i++) w[i].co=arr[i]; moge.clear(); dfs(0,h); moge.push_back(0); priority_queue<pair<double,pair<int,int> > > kolejka; k=min(k,70); for(int i=0;i<n;i++) for(int j=0;j<=k;j++) w[i].dp[j]=1e18; for(int i=0;i<moge.size();i++) { kolejka.push({0.0,{moge[i],0}}); for(int j=0;j<=k;j++) w[moge[i]].dp[j]=0; } while(!kolejka.empty()) { auto para=kolejka.top(); kolejka.pop(); int x=para.second.first; int typ=para.second.second; double ile=-para.first; if(ile>w[x].dp[typ]) continue; if(x==h) continue; for(int i=0;i<w[x].Q.size();i+=2) { int pom=w[x].Q[i]; double dodaj=w[x].Q[i+1]; if(w[pom].dp[typ]>ile+dodaj) kolejka.push({-ile-dodaj,{pom,typ}}),w[pom].dp[typ]=ile+dodaj; if(w[pom].co!=2) continue; dodaj+=ile; dodaj/=2; if(w[pom].dp[typ+1]>dodaj && typ+1<=k) kolejka.push({-dodaj,{pom,typ+1}}),w[pom].dp[typ+1]=dodaj; } } double minn=1e18; for(int i=0;i<=k;i++) minn=min(minn,w[h].dp[i]); if(minn==1e18) return -1; else return minn; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 90324 KB | Correct. |
2 | Correct | 50 ms | 90428 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 74708 KB | Correct. |
2 | Correct | 60 ms | 89980 KB | Correct. |
3 | Correct | 52 ms | 85452 KB | Correct. |
4 | Correct | 54 ms | 88568 KB | Correct. |
5 | Correct | 54 ms | 88836 KB | Correct. |
6 | Correct | 50 ms | 67784 KB | Correct. |
7 | Correct | 59 ms | 89852 KB | Correct. |
8 | Correct | 33 ms | 33740 KB | Correct. |
9 | Correct | 64 ms | 90924 KB | Correct. |
10 | Correct | 51 ms | 89356 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 86064 KB | Correct. |
2 | Correct | 53 ms | 84312 KB | Correct. |
3 | Correct | 50 ms | 79324 KB | Correct. |
4 | Correct | 53 ms | 91340 KB | Correct. |
5 | Correct | 56 ms | 91180 KB | Correct. |
6 | Correct | 11 ms | 14164 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 182 ms | 101840 KB | Correct. |
2 | Correct | 245 ms | 86984 KB | Correct. |
3 | Correct | 190 ms | 80388 KB | Correct. |
4 | Correct | 202 ms | 83104 KB | Correct. |
5 | Correct | 212 ms | 90096 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 83988 KB | Correct. |
2 | Correct | 52 ms | 86744 KB | Correct. |
3 | Correct | 53 ms | 85840 KB | Correct. |
4 | Correct | 45 ms | 65896 KB | Correct. |
5 | Correct | 52 ms | 90460 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 86604 KB | Correct. |
2 | Correct | 45 ms | 75988 KB | Correct. |
3 | Correct | 89 ms | 128704 KB | Correct. |
4 | Correct | 37 ms | 63508 KB | Correct. |
5 | Correct | 52 ms | 92188 KB | Correct. |
6 | Correct | 47 ms | 79048 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 223 ms | 77636 KB | Correct. |
2 | Correct | 28 ms | 8336 KB | Correct. |
3 | Correct | 723 ms | 168832 KB | Correct. |
4 | Correct | 529 ms | 167780 KB | Correct. |
5 | Correct | 724 ms | 97344 KB | Correct. |
6 | Correct | 346 ms | 38544 KB | Correct. |
7 | Correct | 519 ms | 164576 KB | Correct. |
8 | Correct | 496 ms | 167188 KB | Correct. |
9 | Correct | 200 ms | 78604 KB | Correct. |
10 | Correct | 200 ms | 79856 KB | Correct. |
11 | Correct | 495 ms | 169608 KB | Correct. |
12 | Correct | 205 ms | 92732 KB | Correct. |
13 | Correct | 221 ms | 81476 KB | Correct. |
14 | Correct | 453 ms | 154060 KB | Correct. |
15 | Correct | 494 ms | 155480 KB | Correct. |
16 | Correct | 196 ms | 84220 KB | Correct. |
17 | Correct | 245 ms | 87756 KB | Correct. |
18 | Correct | 233 ms | 84692 KB | Correct. |
19 | Correct | 530 ms | 167032 KB | Correct. |
20 | Correct | 17 ms | 8584 KB | Correct. |
21 | Correct | 17 ms | 9208 KB | Correct. |
22 | Correct | 27 ms | 4424 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 734 ms | 77224 KB | Correct. |
2 | Correct | 87 ms | 10364 KB | Correct. |
3 | Correct | 648 ms | 173656 KB | Correct. |
4 | Correct | 1085 ms | 161636 KB | Correct. |
5 | Correct | 2499 ms | 130020 KB | Correct. |
6 | Correct | 1389 ms | 88024 KB | Correct. |
7 | Correct | 1208 ms | 140708 KB | Correct. |
8 | Correct | 1269 ms | 170120 KB | Correct. |
9 | Correct | 679 ms | 79112 KB | Correct. |
10 | Correct | 698 ms | 80296 KB | Correct. |
11 | Correct | 2595 ms | 237888 KB | Correct. |
12 | Correct | 701 ms | 92496 KB | Correct. |
13 | Correct | 794 ms | 81440 KB | Correct. |
14 | Execution timed out | 3072 ms | 133532 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |