QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #417709 | #8232. Yet Another Shortest Path Query | ushg8877 | WA | 2171ms | 339260kb | C++14 | 3.9kb | 2024-05-22 21:07:18 | 2024-05-22 21:07:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const int inf=1e9;
int n,m,q;
int eu[MAXN],ev[MAXN],ew[MAXN];
vector<int> grp[MAXN],edg[MAXN];
unordered_map<int,int> mp[4][MAXN];
int id[MAXN],d[MAXN],tot,qu[MAXN],qv[MAXN],ans[MAXN];bool inq[MAXN];
void chkmin(int &x,int y){if(x>y)x=y;}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>eu[i]>>ev[i]>>ew[i];
grp[eu[i]].push_back(i);
grp[ev[i]].push_back(i);
d[eu[i]]++,d[ev[i]]++;
}
queue<int> Q;
for(int i=1;i<=n;i++) if(d[i]<=5) inq[i]=true,Q.push(i);
while(!Q.empty()){
int u=Q.front();Q.pop();
id[u]=++tot;
for(int id:grp[u]){
int v=eu[id]^ev[id]^u;
if(!inq[v]&&--d[v]<=5) inq[v]=true,Q.push(v);
}
}
for(int i=1;i<=n;i++) if(!inq[i]) assert(0);
for(int i=1;i<=n;i++) for(int j:grp[i]) if(id[eu[j]^ev[j]^i]>id[i])
edg[i].push_back(j);
for(int i=1;i<=n;i++) if(edg[i].size()>=6) cerr<<"ERR!";
cin>>q;
for(int i=1;i<=q;i++){
cin>>qu[i]>>qv[i];
ans[i]=inf;
// =>
for(int x:edg[qu[i]]) if((eu[x]^ev[x]^qu[i])==qv[i]) chkmin(ans[i],ew[x]);
// <=
for(int x:edg[qv[i]]) if((eu[x]^ev[x]^qv[i])==qu[i]) chkmin(ans[i],ew[x]);
// cout<<"Here "<<ans[i]<<'\n';
// => =>
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
for(int y:edg[u]){
int v=eu[y]^ev[y]^u;
if(v==qv[i]) chkmin(ans[i],ew[x]+ew[y]);
}
}
// <= <=
for(int x:edg[qv[i]]){
int u=eu[x]^ev[x]^qv[i];
for(int y:edg[u]){
int v=eu[y]^ev[y]^u;
if(v==qu[i]) chkmin(ans[i],ew[x]+ew[y]);
}
}
// >= =<
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
for(int y:edg[qv[i]]){
int v=eu[y]^ev[y]^qv[i];
if(u==v) chkmin(ans[i],ew[x]+ew[y]);
}
}
// <= =>
mp[2][qu[i]][qv[i]]=inf;
// => => =>
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
for(int y:edg[u]){
int v=eu[y]^ev[y]^u;
for(int z:edg[v]){
int w=eu[z]^ev[z]^v;
if(w==qv[i]) chkmin(ans[i],ew[x]+ew[y]+ew[z]);
}
}
}
// => => <=
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
for(int y:edg[u]){
int v=eu[y]^ev[y]^u;
for(int z:edg[qv[i]]){
int w=eu[z]^ev[z]^qv[i];
if(v==w) chkmin(ans[i],ew[x]+ew[y]+ew[z]);
}
}
}
// => <= <=
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
for(int y:edg[qv[i]]){
int v=eu[y]^ev[y]^qv[i];
for(int z:edg[v]){
int w=eu[z]^ev[z]^v;
if(x==w) chkmin(ans[i],ew[x]+ew[y]+ew[z]);
}
}
}
// <= <= <=
for(int x:edg[qv[i]]){
int u=eu[x]^ev[x]^qv[i];
for(int y:edg[x]){
int v=eu[y]^ev[y]^x;
for(int z:edg[v]){
int w=eu[z]^ev[z]^v;
if(qu[i]==w) chkmin(ans[i],ew[x]+ew[y]+ew[z]);
}
}
}
// <= => =>, <= <= =>
mp[3][qu[i]][qv[i]]=inf;
// => <= => , <= => <=
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
mp[2][u][qv[i]]=inf;
}
for(int x:edg[qv[i]]){
int u=eu[x]^ev[x]^qv[i];
mp[2][u][qu[i]]=inf;
}
}
for(int i=1;i<=n;i++){
for(int x:edg[i]) for(int y:edg[i]) if(x!=y){
int u=eu[x]^ev[x]^i,v=eu[y]^ev[y]^i;
if(mp[2][u].count(v)) chkmin(mp[2][u][v],ew[x]+ew[y]);
if(mp[2][v].count(u)) chkmin(mp[2][v][u],ew[x]+ew[y]);
for(int z:edg[v]){
int w=eu[z]^ev[z]^v;
if(mp[3][u].count(w)) chkmin(mp[3][u][w],ew[x]+ew[y]+ew[z]);
if(mp[3][w].count(u)) chkmin(mp[3][w][u],ew[x]+ew[y]+ew[z]);
}
}
}
for(int i=1;i<=q;i++){
// <= =>
chkmin(ans[i],mp[2][qu[i]][qv[i]]);
// <= => =>, <= <= =>
chkmin(ans[i],mp[3][qu[i]][qv[i]]);
// => <= => , <= => <=
for(int x:edg[qu[i]]){
int u=eu[x]^ev[x]^qu[i];
chkmin(ans[i],ew[x]+mp[2][u][qv[i]]);
}
for(int x:edg[qv[i]]){
int u=eu[x]^ev[x]^qv[i];
chkmin(ans[i],ew[x]+mp[2][u][qu[i]]);
}
cout<<(ans[i]==inf?-1:ans[i])<<'\n';
}
cerr<<"Running Time: "<<1.*clock()/CLOCKS_PER_SEC;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 269528kb
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: 44ms
memory: 269456kb
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: 2171ms
memory: 339260kb
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 10003rd numbers differ - expected: '112907108', found: '-1'