#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define uwu 100005
vector<pair<int,int>>adj[uwu];
double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
ll int yol[N];
for(int i=0;i<N;i++){
father[i]=-1;
yol[i]=1000000000000000000;
}
priority_queue<tuple<ll int,int,int>> pq;
pq.push({(ll int)0,0,-1});
while(pq.size()){
ll int node,once, deg;
tie(deg,node,once)=pq.top();deg=-deg;
pq.pop();
if(arr[node]==0){
deg=0;
}
if(yol[node]<=deg)continue;
yol[node]=deg;
father[node]=once;
if(node==H)continue;
for(auto u:adj[node]){
ll int kim=u.first, lira=u.second+deg;
pq.push({-lira,kim,node});
}
}
for(int i=0;i<N;i++)adj[i].clear();
if(yol[H]==1000000000000000000)yol[H]=-1;
return (1.0)*(double)yol[H];
}
//double uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr);
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<M;i++){
adj[x[i]].pb({y[i],c[i]});
adj[y[i]].pb({x[i],c[i]});
}
int yes=0;
for(int i=0;i<N;i++){
if(arr[i]==2){
yes=1;break;
}
}
if(yes==0)return noiki(N, M, K, H,x, y, c, arr);
//if(N<=3) return uc(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr);
int a=-1,b=-1,cey=-1;
int kac=0,yer=0;;
for(int i=H;i>-1;i--){
if(arr[i]==0){
yer=i;
break;
}
if(kac>=K)continue;
if(arr[i]==2){
if(kac==0)a=i;
if(kac==1)b=i;
if(kac==2&&K%2==1)cey=i;
kac++;
}
}
if(yer==H)return 0.0;
int father[N];
double yol[N];
for(int i=0;i<N;i++){
father[i]=-1;
yol[i]=1000000000000000000;
}
priority_queue<tuple<double,int,pair<int,int>>> pq;
pq.push({-0.0,0,{-1,0}});
while(pq.size()){
ll int node,once,ka;double deg;
pair<int,int> aaa;
tie(deg,node,aaa)=pq.top();deg=-deg;
pq.pop();
once=aaa.first;ka=aaa.second;
if(arr[node]==0){
deg=0;
}
if(node==cey||node==a||node==b&&ka<K){
deg=deg/2;
ka++;
}
//cout<<node<<" "<<once<<" "<<ka<<" "<<deg<<"_"<<a<<" "<<b<<" "<<cey<<endl;
if(yol[node]<=deg)continue;
yol[node]=deg;
father[node]=once;
if(node==H)continue;
for(auto u:adj[node]){
int kim=u.first;double lira=u.second+deg;
if(kim<node&&(node>a||node<=b))continue;
pq.push({-lira,kim,{node,ka}});
}
}
for(int i=0;i<N;i++)adj[i].clear();
return yol[H];
}
Compilation message
cyberland.cpp: In function 'double noiki(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:9:107: warning: variable 'father' set but not used [-Wunused-but-set-variable]
9 | double noiki(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){int father[N];
| ^~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:89:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
89 | if(node==cey||node==a||node==b&&ka<K){
| ~~~~~~~^~~~~~
cyberland.cpp:72:6: warning: variable 'father' set but not used [-Wunused-but-set-variable]
72 | int father[N];
| ^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
15 ms |
2892 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
3164 KB |
Correct. |
2 |
Correct |
25 ms |
3664 KB |
Correct. |
3 |
Correct |
23 ms |
3668 KB |
Correct. |
4 |
Correct |
23 ms |
3672 KB |
Correct. |
5 |
Correct |
24 ms |
3784 KB |
Correct. |
6 |
Correct |
21 ms |
4500 KB |
Correct. |
7 |
Correct |
28 ms |
4524 KB |
Correct. |
8 |
Correct |
13 ms |
5096 KB |
Correct. |
9 |
Correct |
26 ms |
3412 KB |
Correct. |
10 |
Correct |
22 ms |
3444 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
3620 KB |
Correct. |
2 |
Correct |
25 ms |
3636 KB |
Correct. |
3 |
Correct |
23 ms |
3668 KB |
Correct. |
4 |
Correct |
26 ms |
2984 KB |
Correct. |
5 |
Correct |
24 ms |
3544 KB |
Correct. |
6 |
Correct |
6 ms |
3668 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
8012 KB |
Correct. |
2 |
Incorrect |
18 ms |
3540 KB |
Wrong Answer. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
3660 KB |
Correct. |
2 |
Correct |
23 ms |
3820 KB |
Correct. |
3 |
Correct |
29 ms |
3808 KB |
Correct. |
4 |
Correct |
24 ms |
4920 KB |
Correct. |
5 |
Correct |
19 ms |
3408 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
3660 KB |
Correct. |
2 |
Correct |
22 ms |
3704 KB |
Correct. |
3 |
Correct |
36 ms |
11228 KB |
Correct. |
4 |
Correct |
17 ms |
4220 KB |
Correct. |
5 |
Correct |
26 ms |
3576 KB |
Correct. |
6 |
Correct |
25 ms |
3484 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
3816 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
3492 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |