QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #68761 | #5073. Elden Ring | moqiyinlun | WA | 213ms | 8228kb | C++14 | 3.9kb | 2022-12-19 18:30:59 | 2022-12-19 18:31:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N = 2e5+10;
vector<int> G[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T; cin>>T;
while(T--) {
int n,m,A,B; cin>>n>>m>>A>>B;
for(int i=0;i<n;i++)
G[i].clear();
for(int i=0;i<m;i++) {
int a,b; cin>>a>>b;
a--,b--;
G[a].push_back(b);
G[b].push_back(a);
}
int l[n];
for(int i=0;i<n;i++) cin>>l[i], l[i] += B;
l[0] -= B;
if(A == B) {
//Just BFS
int dp[n];
for(int i=0;i<n;i++)
dp[i] = 1e9;
dp[0] = 0;
queue<int> qu;
qu.push(0);
while(!qu.empty()) {
int cur = qu.front();
qu.pop();
for(auto it: G[cur]) {
if(l[it] < l[0] && dp[it] == 1e9) {
dp[it] = dp[cur] + 1;
qu.push(it);
}
}
}
if(dp[n-1] == 1e9) dp[n-1] = -1;
cout<<dp[n-1]<<"\n";
}
else if(A < B) {
//Same thing, but we keep track of time as well
//Just BFS
int dp[n];
for(int i=0;i<n;i++)
dp[i] = 1e9;
dp[0] = 0;
queue<int> qu;
qu.push(0);
while(!qu.empty()) {
int cur = qu.front();
qu.pop();
for(auto it: G[cur]) {
if(1LL*l[it] + 1LL*(B-A)*dp[cur] < 1LL*l[0] && dp[it] == 1e9) {
dp[it] = dp[cur] + 1;
qu.push(it);
}
}
}
if(dp[n-1] == 1e9) dp[n-1] = -1;
cout<<dp[n-1]<<"\n";
}
else {
//First, check whether it is possible to go through wht node
//Use priority queue
priority_queue<pii> pq;
pq.push({0,0});
bool vis[n];
for(int i=0;i<n;i++) vis[i] = false;
int day = -1;
while(!pq.empty()) {
pii cur = pq.top();
pq.pop();
int nd = cur.second;
if(vis[nd]) continue;
int lv = -cur.first;
//cout<<lv<<' '<<l[0]+day*(A-B)<<endl;
if(day != -1 && 1LL*lv >= l[0]+1LL*day*(A-B))
break;
vis[nd] = true;
day++;
for(auto it: G[nd]) {
if(!vis[it])
pq.push({-l[it],it});
}
}
int dp[n];
for(int i=0;i<n;i++) {
dp[i] = 1e9;
}
dp[0] = 0;
while(!pq.empty())
pq.pop();
pq.push({0,0}); //Save the day of the first we can reach
while(!pq.empty()) {
pii cur = pq.top();
pq.pop();
int nd = cur.second;
int day = cur.first;
if(day > dp[nd]) continue;
//cout<<nd<<' '<<dp[nd]<<' '<<l[nd]<<' '<<(l[nd]-l[0])/(A-B) + 2<<endl;
for(auto it: G[nd]) {
if(vis[it] && dp[it] > day+1 && l[it] < l[0]) {
dp[it] = day+1;
pq.push({-dp[it], it});
continue;
}
if(vis[it] && dp[it] > max(day+1,(l[it]-l[0])/(A-B) + 2)) {
dp[it] = max(day+1,(l[it]-l[0])/(A-B)+2);
pq.push({dp[it], it});
}
}
}
if(dp[n-1] == 1e9) dp[n-1] = -1;
cout<<dp[n-1]<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8076kb
input:
2 5 4 5 8 1 2 1 3 1 4 4 5 15 1 1 1 1 5 4 10 5 1 2 1 3 1 4 4 5 10 4 4 4 19
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: -100
Wrong Answer
time: 213ms
memory: 8228kb
input:
100000 6 10 107812 105568 6 5 3 6 4 6 4 2 5 1 5 6 4 5 1 3 1 2 2 5 124065 140875 29890 80077 116532 35394 9 10 82107 88302 1 2 2 3 5 3 5 1 1 4 9 6 3 5 8 2 5 6 7 5 22670 3735 33660 92823 139960 89319 83335 158330 117349 6 10 181257 173221 5 3 3 4 3 1 5 1 2 1 3 6 3 1 6 2 3 6 4 3 76902 46253 123092 2661...
output:
-1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -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 2 -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 0 -1 -1 -1 -1 -1 ...
result:
wrong answer 59th numbers differ - expected: '3', found: '1'