#include "cyberland.h"
#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
using namespace std;
double sub_2_5(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
vector<vector<pair<int,int>>> G(N);
for(int i=0;i<M;i++){
G[x[i]].push_back({y[i], c[i]});
G[y[i]].push_back({x[i], c[i]});
}
dp[0] = 0;
pq.push({0,dp[0]});
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
double sub_3_6(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
vector<vector<pair<int,int>>> G(N);
for(int i=0;i<M;i++){
G[x[i]].push_back({y[i], c[i]});
G[y[i]].push_back({x[i], c[i]});
}
dp[0] = 0;
pq.push({0,dp[0]});
vector<bool> vis(N,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i] = 0;
pq.push({i,dp[i]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
double sub_1_4_7(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
int div2;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N, vector<double> (K+2, (double)(1e15)));
vector<vector<pair<int,int>>> G(N);
for(int i=0;i<M;i++){
G[x[i]].push_back({y[i], c[i]});
G[y[i]].push_back({x[i], c[i]});
}
dp[0][0] = 0;
pq.push({0,0,dp[0][0]});
vector<bool> vis(N,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i][0] = 0;
pq.push({i,0,dp[i][0]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id][u.div2] < u.w) continue;
if(u.id == H) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2]){
dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
pq.push({v.first, u.div2, dp[v.first][u.div2]});
}
double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
if(u.div2 + 1 <= K && arr[v.first] == 2){
if(tmp < dp[v.first][u.div2+1]){
dp[v.first][u.div2+1] = tmp;
pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
}
}
}
}
double ans = (double)(1e15);
for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
if(ans == (double)(1e15)) ans = -1;
return ans;
}
double sub_8(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
int div2;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<vector<double>> dp(N, vector<double> (K+2, (double)(1e15)));
vector<vector<int>> vis_go(N, vector<int> (K+2, 0));
vector<vector<pair<int,int>>> G(N);
for(int i=0;i<M;i++){
G[x[i]].push_back({y[i], c[i]});
G[y[i]].push_back({x[i], c[i]});
}
dp[0][0] = 0;
pq.push({0,0,dp[0][0]});
vis_go[0][0] = 1;
vector<bool> vis(N,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i][0] = 0;
vis_go[i][0] = 1;
pq.push({i,0,dp[i][0]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id][u.div2] < u.w) continue;
if(u.id == H) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2] && vis_go[v.first][u.div2+1] < K){
dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
vis_go[v.first][u.div2]++;
pq.push({v.first, u.div2, dp[v.first][u.div2]});
}
double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
if(u.div2 + 1 <= K && arr[v.first] == 2){
if(tmp < dp[v.first][u.div2+1] && vis_go[v.first][u.div2+1] < K){
dp[v.first][u.div2+1] = tmp;
vis_go[v.first][u.div2+1]++;
pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
}
}
}
}
double ans = (double)(1e15);
for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
if(ans == (double)(1e15)) ans = -1;
return ans;
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
int check_sub_2_5 = 0;
for(int i=0;i<N;i++) check_sub_2_5 += (arr[i] == 1);
if(check_sub_2_5 == N) return sub_2_5(N,M,K,H,x,y,c,arr);
int check_sub_3_6 = 0;
for(int i=0;i<N;i++) check_sub_3_6 += (arr[i] != 2);
if(check_sub_3_6 == N) return sub_3_6(N,M,K,H,x,y,c,arr);
if(K <= 30) return sub_1_4_7(N,M,K,H,x,y,c,arr);
return sub_8(N,M,min(K,100),H,x,y,c,arr);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
456 KB |
Correct. |
2 |
Correct |
23 ms |
368 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
484 KB |
Correct. |
2 |
Correct |
27 ms |
468 KB |
Correct. |
3 |
Correct |
25 ms |
428 KB |
Correct. |
4 |
Correct |
31 ms |
436 KB |
Correct. |
5 |
Correct |
31 ms |
444 KB |
Correct. |
6 |
Correct |
24 ms |
1504 KB |
Correct. |
7 |
Correct |
33 ms |
1432 KB |
Correct. |
8 |
Correct |
12 ms |
2660 KB |
Correct. |
9 |
Correct |
25 ms |
388 KB |
Correct. |
10 |
Correct |
27 ms |
388 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
456 KB |
Correct. |
2 |
Correct |
27 ms |
480 KB |
Correct. |
3 |
Correct |
26 ms |
504 KB |
Correct. |
4 |
Correct |
28 ms |
380 KB |
Correct. |
5 |
Correct |
27 ms |
340 KB |
Correct. |
6 |
Correct |
7 ms |
1364 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
250 ms |
27240 KB |
Correct. |
2 |
Correct |
295 ms |
1088 KB |
Correct. |
3 |
Correct |
267 ms |
1208 KB |
Correct. |
4 |
Correct |
281 ms |
1196 KB |
Correct. |
5 |
Correct |
230 ms |
484 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
460 KB |
Correct. |
2 |
Correct |
27 ms |
468 KB |
Correct. |
3 |
Correct |
25 ms |
608 KB |
Correct. |
4 |
Correct |
24 ms |
1492 KB |
Correct. |
5 |
Correct |
22 ms |
340 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
484 KB |
Correct. |
2 |
Correct |
22 ms |
468 KB |
Correct. |
3 |
Correct |
51 ms |
8944 KB |
Correct. |
4 |
Correct |
17 ms |
1280 KB |
Correct. |
5 |
Correct |
26 ms |
392 KB |
Correct. |
6 |
Correct |
24 ms |
508 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
305 ms |
1592 KB |
Correct. |
2 |
Correct |
41 ms |
2364 KB |
Correct. |
3 |
Correct |
805 ms |
29748 KB |
Correct. |
4 |
Correct |
580 ms |
7876 KB |
Correct. |
5 |
Correct |
1296 ms |
50060 KB |
Correct. |
6 |
Correct |
545 ms |
41376 KB |
Correct. |
7 |
Correct |
539 ms |
8136 KB |
Correct. |
8 |
Correct |
576 ms |
2024 KB |
Correct. |
9 |
Correct |
279 ms |
2176 KB |
Correct. |
10 |
Correct |
273 ms |
1612 KB |
Correct. |
11 |
Correct |
528 ms |
976 KB |
Correct. |
12 |
Correct |
303 ms |
1588 KB |
Correct. |
13 |
Correct |
306 ms |
1592 KB |
Correct. |
14 |
Correct |
458 ms |
10992 KB |
Correct. |
15 |
Correct |
545 ms |
3348 KB |
Correct. |
16 |
Correct |
284 ms |
1592 KB |
Correct. |
17 |
Correct |
330 ms |
1504 KB |
Correct. |
18 |
Correct |
342 ms |
1492 KB |
Correct. |
19 |
Correct |
806 ms |
1768 KB |
Correct. |
20 |
Correct |
22 ms |
724 KB |
Correct. |
21 |
Correct |
22 ms |
1076 KB |
Correct. |
22 |
Correct |
44 ms |
3324 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1495 ms |
7440 KB |
Correct. |
2 |
Correct |
187 ms |
9008 KB |
Correct. |
3 |
Correct |
938 ms |
137348 KB |
Correct. |
4 |
Incorrect |
1343 ms |
8980 KB |
Wrong Answer. |
5 |
Halted |
0 ms |
0 KB |
- |