# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
984752 | 2024-05-17T04:35:53 Z | Muhammad_Aneeq | 사이버랜드 (APIO23_cyberland) | C++17 | 40 ms | 15696 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]; long long par[MAXN],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]={}; par[i]=-1; val[i]=arr[i]; vis[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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 4440 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 4440 KB | Correct. |
2 | Correct | 27 ms | 4644 KB | Correct. |
3 | Correct | 28 ms | 4696 KB | Correct. |
4 | Correct | 27 ms | 4444 KB | Correct. |
5 | Correct | 29 ms | 4664 KB | Correct. |
6 | Correct | 26 ms | 6228 KB | Correct. |
7 | Correct | 36 ms | 6232 KB | Correct. |
8 | Correct | 19 ms | 8148 KB | Correct. |
9 | Correct | 26 ms | 4712 KB | Correct. |
10 | Correct | 23 ms | 4444 KB | Correct. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 4444 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 40 ms | 15696 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 28 ms | 4700 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 34 ms | 4700 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 4696 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 39 ms | 4696 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |