# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
777409 | groshi | 사이버랜드 (APIO23_cyberland) | C++17 | 3078 ms | 121780 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "O3"
#include "cyberland.h"
using namespace std;
vector<int> moge;
vector<int> Q[100010];
bool odw[100010];
vector<int> co;
void dfs(int x,int nie)
{
odw[x]=1;
if(x==nie)
return;
if(co[x]==0)
moge.push_back(x);
for(int i=0;i<Q[x].size();i+=2)
if(odw[Q[x][i]]==0)
dfs(Q[x][i],nie);
}
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c, vector<int> arr)
{
for(int i=0;i<n;i++)
Q[i].clear(),odw[i]=0;
vector<double> dp[n+3];
for(int i=0;i<m;i++)
{
Q[x[i]].push_back(y[i]);
Q[y[i]].push_back(x[i]);
Q[x[i]].push_back(c[i]);
Q[y[i]].push_back(c[i]);
}
swap(arr,co);
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++)
dp[i].push_back(1e14);
for(int i=0;i<moge.size();i++)
{
kolejka.push({0.0,{moge[i],0}});
for(int j=0;j<=k;j++)
dp[moge[i]][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>dp[x][typ])
continue;
if(x==h)
continue;
for(int i=0;i<Q[x].size();i+=2)
{
int pom=Q[x][i];
double dodaj=Q[x][i+1];
if(dp[pom][typ]>ile+dodaj)
kolejka.push({-ile-dodaj,{pom,typ}}),dp[pom][typ]=ile+dodaj;
if(co[pom]!=2)
continue;
dodaj+=ile;
dodaj/=2;
if(dp[pom][typ+1]>dodaj && typ+1<=k)
kolejka.push({-dodaj,{pom,typ+1}}),dp[pom][typ+1]=dodaj;
}
}
double minn=1e14;
for(int i=0;i<=k;i++)
minn=min(minn,dp[h][i]);
if(minn==1e14)
return -1;
else return minn;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |