# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
984755 | 2024-05-17T04:46:59 Z | Muhammad_Aneeq | Cyberland (APIO23_cyberland) | C++17 | 45 ms | 14676 KB |
#include "cyberland.h" #include <vector> #include <map> #include <set> #include <iostream> using namespace std; int const MAXN=1e5+10; vector<pair<int,int>>nei[MAXN]; int val[MAXN]; bool vis[MAXN]={},ra[MAXN]={}; int h; map<pair<int,int>,int>d; void dfs(int x) { ra[x]=1; vis[x]=1; for (auto [i,j]:nei[x]) { if (!vis[i]&&i!=h) dfs(i); } } vector<int>p; int k; double ans=1e15+10; void dfs1(int x) { vis[x]=1; p.push_back(x); if (val[x]==0||x==0) { double su=0; vector<int>va; for (int i=p.size()-1;i>=0;i--) { if (val[p[i]]==2) va.push_back(p[i]); } int x=max(0,int(va.size()-k)); bool w=0; for (int i=p.size()-1;i>=1;i--) { if (va.size()&&p[i-1]==va[x]) w=1; su+=d[{p[i],p[i-1]}]; if (w&&val[p[i-1]]==2) su/=2.0; } ans=min(ans,su); if (p.size()) p.pop_back(); return; } for (auto [i,j]:nei[x]) { if (ra[i]&&!vis[i]) dfs1(i); } if (p.size()) p.pop_back(); } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { h=H; k=K; ans=1e15+10; d={}; for (int i=0;i<N;i++) { nei[i]={}; val[i]=arr[i]; vis[i]=0; ra[i]=0; } for (int i=0;i<x.size();i++) { d[{x[i],y[i]}]=d[{y[i],x[i]}]=c[i]; nei[x[i]].push_back({y[i],c[i]}); nei[y[i]].push_back({x[i],c[i]}); } dfs(0); for (int i=0;i<N;i++) vis[i]=0; dfs1(h); if (ans==1e15+10) return -1; return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 3164 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 3484 KB | Correct. |
2 | Correct | 26 ms | 3468 KB | Correct. |
3 | Correct | 25 ms | 3420 KB | Correct. |
4 | Correct | 28 ms | 3932 KB | Correct. |
5 | Correct | 26 ms | 3420 KB | Correct. |
6 | Correct | 26 ms | 5076 KB | Correct. |
7 | Correct | 34 ms | 4956 KB | Correct. |
8 | Correct | 16 ms | 7000 KB | Correct. |
9 | Correct | 24 ms | 3164 KB | Correct. |
10 | Correct | 30 ms | 3164 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 3440 KB | Correct. |
2 | Correct | 25 ms | 4444 KB | Correct. |
3 | Correct | 24 ms | 3776 KB | Correct. |
4 | Correct | 24 ms | 4188 KB | Correct. |
5 | Correct | 24 ms | 4160 KB | Correct. |
6 | Correct | 9 ms | 4956 KB | Correct. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 45 ms | 14676 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 28 ms | 3416 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 32 ms | 3420 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 3420 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 3452 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |