QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #676405 | #6527. Cyberland | neilliu | 0 | 626ms | 460076kb | C++17 | 1.9kb | 2024-10-25 21:24:06 | 2024-10-25 21:24:07 |
Judging History
answer
#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define MAXN 7000005
vector<int> edge[MAXN];
vector<int> lian[MAXN];
bool ok[MAXN];
double dis[MAXN];
bool vis[MAXN];
struct kkk{
int id;
double w;
friend bool operator <(kkk ano1,kkk ano2){
return ano1.w > ano2.w;
}
};
priority_queue<kkk> qq;
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) {
for(int i = 0; i < (K+1) * N; i++) edge[i].clear(),lian[i].clear();
for(int i = 0; i < N; i++) ok[i] = 0;
for(int i = 0; i < M; i++){
edge[x[i]].push_back(y[i]);
edge[y[i]].push_back(x[i]);
lian[x[i]].push_back(c[i]);
lian[y[i]].push_back(c[i]);
}
queue<int> q; q.push(0);
while(q.size()){
int nowx = q.front(); q.pop();
if(ok[nowx]) continue;
ok[nowx] = 1;
for(int v : edge[nowx]){
q.push(v);
}
}
if(!ok[H]) return -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < K; j++){
edge[j * N + x[i]].push_back((j + 1) * N + x[i]);
lian[j * N + x[i]].push_back(-114514);
}
}
for(int i = 0; i < (K+1) * N; i++) dis[i] = 1e17,vis[i] = 0;
while(qq.size()) qq.pop();
for(int i = 0; i < N; i++){
if(arr[i] == 0 && ok[i] == 1){
qq.push((kkk){i,0});
dis[i] = 0;
}
}
qq.push((kkk){0,0});
dis[0] = 0;
double ans = 1e17;
while(qq.size()){
int nowx = qq.top().id; qq.pop();
if(vis[nowx]) continue;
vis[nowx] = 1;
if(nowx % N == H) ans = min(ans,dis[nowx]);
for(int vv = 0; vv < edge[nowx].size(); vv++){
int v = edge[nowx][vv];
if(lian[nowx][vv] == -114514){
if(dis[v] > (double)dis[nowx] / 2.0){
dis[v] = (double)dis[nowx] / 2.0;
qq.push((kkk){v,dis[v]});
}
}else{
if(dis[v] > dis[nowx] + lian[nowx][vv]){
dis[v] = dis[nowx] + lian[nowx][vv];
qq.push((kkk){v,dis[v]});
}
}
}
}
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 59ms
memory: 333008kb
input:
10000 2 1 30 1 1 1 1 0 13080 3 3 30 1 1 1 1 0 2 25242 2 1 13399 1 0 2123 2 1 30 1 1 1 0 1 11947 2 1 30 1 1 1 0 1 27361 3 0 30 2 1 0 1 2 0 30 1 1 1 3 2 30 1 1 1 2 1 2 23211 0 1 9991 3 1 30 1 1 1 1 2 1 3093 2 1 30 1 1 1 1 0 10703 2 1 30 1 1 1 0 1 15754 2 1 30 1 1 1 1 0 18752 2 1 30 1 1 1 1 0 2300 2 1 ...
output:
a9100fda0a7059a979d560b8550f715d4ee391ff9b8b680b2f87b26a69ee5a5e 0.000012181699276 0.000001977197826 11947.000000000000000 27361.000000000000000 -1.000000000000000 -1.000000000000000 0.000009304843843 -1.000000000000000 0.000009967945516 15754.000000000000000 0.000017464160919 0.000002142041922 2814...
result:
wrong answer Wrong Answer.
Subtask #2:
score: 0
Runtime Error
Test #3:
score: 0
Runtime Error
input:
100 982 981 30 107 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
a9100fda0a7059a979d560b8550f715d4ee391ff9b8b680b2f87b26a69ee5a5e
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 626ms
memory: 460076kb
input:
1 58243 58242 30 14059 1 2 0 1 0 2 2 0 0 0 1 0 2 0 2 1 2 1 0 0 0 2 1 0 0 0 0 1 2 1 0 2 0 2 2 2 2 2 0 0 2 2 1 2 1 2 0 2 2 1 2 0 0 1 0 0 0 0 2 2 0 0 2 2 1 0 0 0 2 2 0 1 2 1 0 2 0 0 2 0 1 0 2 1 2 2 1 1 2 1 2 1 2 2 0 1 0 1 1 2 1 2 2 1 0 1 2 1 2 1 0 2 2 2 1 2 0 1 0 1 0 1 2 0 0 0 2 2 1 1 1 2 0 1 2 2 2 2 1...
output:
a9100fda0a7059a979d560b8550f715d4ee391ff9b8b680b2f87b26a69ee5a5e 0.591709121130407 a9100fda0a7059a979d560b8550f715d4ee391ff9b8b680b2f87b26a69ee5a5e
result:
wrong answer Wrong Answer.
Subtask #5:
score: 0
Runtime Error
Test #24:
score: 0
Runtime Error
input:
100 442 637 30 269 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
a9100fda0a7059a979d560b8550f715d4ee391ff9b8b680b2f87b26a69ee5a5e
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%