QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #334587 | #8232. Yet Another Shortest Path Query | ucup-team134 | WA | 925ms | 484472kb | C++14 | 6.9kb | 2024-02-22 07:00:23 | 2024-02-22 07:00:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=1e6+10;
const double max_load_cap=0.2;
int inf=1e9;
struct chash{
const uint64_t C= (ll)(4e18*acos(0))|71;
ll operator()(ll x)const{return __builtin_bswap64(x*C);}
};
vector<pii>vg[maxn],vout[maxn],vin[maxn];
vector<int>niz,revniz;
unordered_map<int,int,chash>map_out[maxn],map_in[maxn],map_rez[maxn];
int n,m,deg[maxn],pos[maxn],q,rez_qry[maxn];
void init(){
for(int i=1;i<=n;i++){
map_out[i].max_load_factor(max_load_cap);
map_in[i].max_load_factor(max_load_cap);
map_rez[i].max_load_factor(max_load_cap);
for(int j=0;j<vout[i].size();j++)map_out[i][vout[i][j].ff]=vout[i][j].ss;
for(int j=0;j<vin[i].size();j++)map_in[i][vin[i][j].ff]=vin[i][j].ss;
///printf("%d %d AAA\n",i,niz[i]);
}
}
void prek(){
vector<int>good;
for(int i=1;i<=n;i++){
if(deg[i]<=5)good.pb(i);
}
niz.pb(0);
revniz.resize(n+1);
for(int i=1;i<=n;i++){
int id=good.back();
good.pop_back();
niz.pb(id);
revniz[id]=niz.size()-1;
pos[id]=1;
for(int j=0;j<vg[id].size();j++){
int id2=vg[id][j].ff;
if(pos[id2])continue;
deg[id2]--;
if(deg[id2]==5)good.pb(id2);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<vg[i].size();j++){
int id=vg[i][j].ff;
int w=vg[i][j].ss;
int a=revniz[i];
int b=revniz[id];
if(a>b){
continue;
}
vout[a].pb({b,w});
vin[b].pb({a,w});
}
}
}
void update_rez(int a,int b,int w){
if(a>b)swap(a,b);
if(map_rez[a].find(b)==map_rez[a].end())map_rez[a][b]=w;
else{
int &p=map_rez[a][b];
p=min(p,w);
}
}
void go_LR(){
for(int i=1;i<=n;i++){
for(int j=0;j<vout[i].size();j++){
int id1=vout[i][j].ff;
int w1=vout[i][j].ss;
update_rez(i,id1,w1);
for(int k=j+1;k<vout[i].size();k++){
int id2=vout[i][k].ff;
int w2=vout[i][k].ss;
update_rez(id1,id2,w1+w2);
}
}
}
}
void go_lrr_llr(){
for(int i=1;i<=n;i++){
for(int j=0;j<vout[i].size();j++){
int id1=vout[i][j].ff;
int w1=vout[i][j].ss;
for(int k=0;k<vout[i].size();k++){
int id2=vout[i][k].ff;
if(id2==id1)continue;
int w2=vout[i][k].ss;
for(int p=0;p<vout[id2].size();p++){
int id3=vout[id2][p].ff;
int w3=vout[id2][p].ss;
///printf("%d %d %d %d AAA\n",i,id1,id2,id3);
update_rez(id1,id3,w1+w2+w3);
}
}
}
}
}
struct qry{
int a,b,w,id;
}pocqry[maxn];
vector<qry>newqry;
void go_make_k2(){
for(int i=1;i<=q;i++){
int a=pocqry[i].a;
int b=pocqry[i].b;
qry pom2;
pom2.id=i;
pom2.a=a;
pom2.b=b;
pom2.w=0;
newqry.pb(pom2);
for(int j=0;j<vout[a].size();j++){
int id=vout[a][j].ff;
int w=vout[a][j].ss;
qry pom;
pom.id=pocqry[i].id;
pom.w=w;
pom.a=id;
pom.b=b;
///printf("%d %d EDGE A\n",pom.a,pom.b);
if(pom.a>pom.b)swap(pom.a,pom.b);
newqry.pb(pom);
}
for(int j=0;j<vout[b].size();j++){
int id=vout[b][j].ff;
int w=vout[b][j].ss;
qry pom;
pom.id=pocqry[i].id;
pom.w=w;
pom.a=a;
pom.b=id;
///printf("%d %d EDGE B\n",pom.a,pom.b);
if(pom.a>pom.b)swap(pom.a,pom.b);
newqry.pb(pom);
}
}
/*for(int i=0;i<newqry.size();i++){
printf("%d %d %d %d NQ\n",newqry[i].a,newqry[i].b,newqry[i].id,newqry[i].w);
}*/
}
void go_upd_LR_k2(){
return;
for(int i=0;i<newqry.size();i++){
if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end())
rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
}
}
void go_RR_k2(){
for(int i=1;i<=n;i++){
for(int j=0;j<vin[i].size();j++){
for(int k=0;k<vout[i].size();k++){
int id1=vin[i][j].ff;
int id2=vout[i][k].ff;
int w1=vin[i][j].ss;
int w2=vout[i][k].ss;
///printf("%d %d |");
update_rez(id1,id2,w1+w2);
}
}
}
for(int i=0;i<newqry.size();i++){
if(map_rez[newqry[i].a].find(newqry[i].b)!=map_rez[newqry[i].a].end())
rez_qry[newqry[i].id]=min(rez_qry[newqry[i].id],map_rez[newqry[i].a][newqry[i].b]+newqry[i].w);
}
}
void go_RL_k2(){
for(int i=0;i<newqry.size();i++){
int id=newqry[i].id;
int a=newqry[i].a;
int b=newqry[i].b;
int w=newqry[i].w;
for(int j=0;j<vout[a].size();j++){
int id2=vout[a][j].ff;
int w2=vout[a][j].ss;
if(map_in[id2].find(b)!=map_in[id2].end())
rez_qry[id]=min(rez_qry[id],w2+w+map_in[id2][b]);
}
}
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,w;
scanf("%d %d %d",&a,&b,&w);
vg[a].pb({b,w});
vg[b].pb({a,w});
deg[a]++;
deg[b]++;
}
prek();
init();
go_LR();
go_lrr_llr();
scanf("%d",&q);
for(int i=1;i<=q;i++){
rez_qry[i]=inf;
int a,b;
scanf("%d %d",&a,&b);
a=revniz[a];
b=revniz[b];
if(a>b)swap(a,b);
pocqry[i].id=i;
pocqry[i].a=a;
pocqry[i].b=b;
pocqry[i].w=0;
}
go_make_k2();
go_upd_LR_k2();
go_RR_k2();
go_RL_k2();
for(int i=1;i<=q;i++){
int a=pocqry[i].a;
int b=pocqry[i].b;
if(map_rez[a].find(b)!=map_rez[a].end())rez_qry[i]=min(rez_qry[i],map_rez[a][b]);
if(rez_qry[i]==inf)printf("-1\n");
else printf("%d\n",rez_qry[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 103ms
memory: 262940kb
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: 54ms
memory: 261664kb
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: 925ms
memory: 484472kb
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 6236th numbers differ - expected: '-1', found: '146724051'