QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #324915 | #8232. Yet Another Shortest Path Query | ucup-team197# | WA | 465ms | 144956kb | C++14 | 2.4kb | 2024-02-11 01:35:08 | 2024-02-11 01:35:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int iu=19;
#define fi first
#define se second
int n,m,q;
vector<pair<ll,int> >adj[N],out[N],in[N];
int deg[N];
int ord[N];
vector<pair<int,int> >qry[N];
ll ans[N];
int qid[N];
ll best[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> m;
for(int i=1; i<=m ;i++){
int u,v,w;cin >> u >> v >> w;
adj[u].push_back({w,v});
adj[v].push_back({w,u});
deg[u]++;deg[v]++;
}
stack<int>s;
for(int i=1; i<=n ;i++){
if(deg[i]<=5) s.push(i);
}
for(int i=1; i<=n ;i++){
int x=s.top();s.pop();
ord[x]=i;
for(auto c:adj[x]){
if(ord[c.se]) continue;
in[c.se].push_back({c.fi,x});
out[x].push_back(c);
if(--deg[c.se]==5){
s.push(c.se);
}
}
}
cin >> q;
for(int i=1; i<=q ;i++){
int u,v;cin >> u >> v;
qry[u].push_back({i,v});
qry[v].push_back({i,u});
ans[i]=1e18;
{
for(auto c:out[u]){
if(c.se==v) ans[i]=min(ans[i],c.fi);
for(auto d:out[v]){
if(c.se==d.se) ans[i]=min(ans[i],c.fi+d.fi);
}
for(auto d:out[c.se]){
if(d.se==v) ans[i]=min(ans[i],c.fi+d.fi);
for(auto e:out[d.se]){
if(e.se==v) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
}
for(auto e:out[v]){
if(e.se==d.se) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
}
}
}
}
swap(u,v);
{
for(auto c:out[u]){
if(c.se==v) ans[i]=min(ans[i],c.fi);
for(auto d:out[c.se]){
if(d.se==v) ans[i]=min(ans[i],c.fi+d.fi);
for(auto e:out[d.se]){
if(e.se==v) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
}
for(auto e:out[v]){
if(e.se==d.se) ans[i]=min(ans[i],c.fi+d.fi+e.fi);
}
}
}
}
}
for(int i=1; i<=n ;i++) best[i]=1e18,qid[i]=0;
for(int t=1; t<=n ;t++){
for(auto c:qry[t]) qid[c.se]=c.fi;
for(auto c:in[t]){
for(auto d:out[c.se]){
best[d.se]=min(best[d.se],c.fi+d.fi);
if(qid[d.se]) ans[qid[d.se]]=min(ans[qid[d.se]],best[d.se]);
for(auto e:out[d.se]){
if(qid[e.se]) ans[qid[e.se]]=min(ans[qid[e.se]],best[d.se]+e.fi);
}
}
}
for(auto c:qry[t]){
for(auto d:out[c.se]){
ans[c.fi]=min(ans[c.fi],d.fi+best[d.se]);
}
}
for(auto c:in[t]){
for(auto d:out[c.se]){
best[d.se]=1e18;
}
}
for(auto c:qry[t]) qid[c.se]=0;
}
for(int i=1; i<=q ;i++){
if(ans[i]==1e18) cout << "-1\n";
else cout << ans[i] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 106076kb
input:
6 9 1 2 4 2 3 6 3 6 5 6 5 3 5 4 2 4 1 3 3 4 9 1 3 100 5 3 1 5 1 3 1 6 3 4 3 5 2 5
output:
6 8 3 1 7
result:
ok 5 number(s): "6 8 3 1 7"
Test #2:
score: 0
Accepted
time: 16ms
memory: 106448kb
input:
6 4 1 2 1 2 3 1 3 4 1 4 5 1 3 1 4 1 5 1 6
output:
3 -1 -1
result:
ok 3 number(s): "3 -1 -1"
Test #3:
score: -100
Wrong Answer
time: 465ms
memory: 144956kb
input:
40005 79608 1 2 70031203 1 3 99924845 1 4 61645659 1 5 9324967 2 3 15761918 3 4 62534796 4 5 35260314 5 2 35948540 6 2 23727405 6 7 83302920 7 3 31010426 7 8 75060393 8 4 94275932 8 9 99663793 9 5 81701979 9 6 439297 10 6 46955645 10 11 89514237 11 7 21257310 11 12 53896253 12 8 67933315 12 13 26161...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 10014th numbers differ - expected: '149846554', found: '155353090'