QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369179 | #6101. Ring Road | Graphcity | WA | 704ms | 66864kb | C++20 | 4.5kb | 2024-03-27 21:31:43 | 2024-03-27 21:31:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2.5e5;
const ll inf=1e18;
int tot,vis[Maxn+5],X[Maxn+5],Y[Maxn+5]; ll Z[Maxn+5];
vector<pair<int,ll>> w[Maxn+5];
vector<pair<int,int>> v[Maxn+5];
inline void Addedge(int x,int y,ll z)
{
X[++tot]=x,Y[tot]=y,Z[tot]=z;
v[x].emplace_back(y,tot),v[y].emplace_back(x,tot);
}
int n,m,q,siz[Maxn+5]; ll ans[Maxn+5];
int rt,sum,maxs,tp[Maxn+5],chk[Maxn+5];
struct Data{int x; ll k;};
inline bool operator<(Data a,Data b) {return a.k>b.k;}
struct Graph
{
ll dis[Maxn+5]; int vis[Maxn+5];
vector<pair<int,ll>> v[Maxn+5];
inline void Clear(vector<int> &vx) {for(auto i:vx) vector<pair<int,ll>>().swap(v[i]);}
inline void Dijkstra(int s,vector<int> &vx)
{
priority_queue<Data> q;
for(auto i:vx) dis[i]=inf,vis[i]=0;
dis[s]=0,q.push(Data{s,0ll});
while(!q.empty())
{
int x=q.top().x; q.pop();
if(vis[x]) continue; vis[x]=1;
for(auto [y,k]:v[x]) if(!vis[y] && dis[x]+k<dis[y])
dis[y]=dis[x]+k,q.push(Data{y,dis[y]});
}
}
} G;
inline void Add(int x,int y,ll k) {G.v[x].emplace_back(y,k),G.v[y].emplace_back(x,k);}
inline void GetRt(int x,int f)
{
siz[x]=1; for(auto [y,id]:v[x]) if(y!=f && !vis[id])
{
GetRt(y,x),siz[x]+=siz[y];
int mx=max(siz[y],sum-siz[y]);
if(mx<maxs) rt=id,maxs=mx;
}
}
inline void dfs0(int x,int f)
{
int pr=x; for(auto [y,z]:w[x]) if(y!=f)
Addedge(pr,++m,0ll),Addedge(m,y,z),pr=m;
for(auto [y,z]:w[x]) if(y!=f) dfs0(y,x);
}
inline void dfs1(int x,int f,vector<int> &vx,int k)
{
vx.push_back(x),tp[x]=k,siz[x]=1;
for(auto [y,id]:v[x]) if(y!=f && !vis[id]) dfs1(y,x,vx,k),siz[x]+=siz[y];
}
inline void dfs2(int x,int f)
{for(auto [y,id]:v[x]) if(y!=f && !vis[id]) Add(x,y,Z[id]),dfs2(y,x);}
inline void dfs(int ID,vector<array<ll,3>> w,vector<array<int,3>> qr)
{
vis[ID]=1; int a=X[ID],b=Y[ID];
// cerr<<a<<' '<<b<<endl;
// for(auto [x,y,k]:w) cerr<<x<<' '<<y<<' '<<k<<endl;
vector<int> v1,v2,vx; dfs1(a,0,v1,1),dfs1(b,0,v2,2);
for(auto i:v1) vx.push_back(i);
for(auto i:v2) vx.push_back(i);
G.Clear(vx),dfs2(a,0),dfs2(b,0),Add(a,b,Z[ID]);
vector<ll> w1,w2,z1,z2;
for(auto [a,b,k]:w)
{
if(!chk[a]) chk[a]=1,(tp[a]==1?w1:w2).push_back(a);
if(!chk[b]) chk[b]=1,(tp[b]==1?w1:w2).push_back(b);
if(tp[a]==1 && tp[b]==1) z1.push_back(k);
if(tp[a]==2 && tp[b]==2) z2.push_back(k);
} for(auto [a,b,k]:w) chk[a]=chk[b]=0,Add(a,b,k);
G.Dijkstra(a,vx); for(auto [x,y,id]:qr) ans[id]=min(ans[id],G.dis[x]+G.dis[y]);
if(!w1.empty())
{
int p=w1.front(),q=w1.back();
G.Dijkstra(p,vx); for(auto [x,y,id]:qr) ans[id]=min(ans[id],G.dis[x]+G.dis[y]);
G.Dijkstra(q,vx); for(auto [x,y,id]:qr) ans[id]=min(ans[id],G.dis[x]+G.dis[y]);
z1.push_back(G.dis[p]);
}
if(!w2.empty())
{
int p=w2.front(),q=w2.back();
G.Dijkstra(p,vx); for(auto [x,y,id]:qr) ans[id]=min(ans[id],G.dis[x]+G.dis[y]);
G.Dijkstra(q,vx); for(auto [x,y,id]:qr) ans[id]=min(ans[id],G.dis[x]+G.dis[y]);
z2.push_back(G.dis[p]);
}
vector<array<ll,3>> h1,h2; int sz;
sz=w1.size(); For(i,0,sz-1) h1.push_back({w1[i],w1[(i+1)%sz],z1[i]});
sz=w2.size(); For(i,0,sz-1) h2.push_back({w2[i],w2[(i+1)%sz],z2[i]});
vector<array<int,3>> q1,q2;
for(auto [x,y,id]:qr)
{
if(tp[x]==1 && tp[y]==1) q1.push_back({x,y,id});
if(tp[x]==2 && tp[y]==2) q2.push_back({x,y,id});
}
rt=0,sum=siz[a],maxs=n+5,GetRt(a,0); if(rt) dfs(rt,h1,q1);
rt=0,sum=siz[b],maxs=n+5,GetRt(b,0); if(rt) dfs(rt,h2,q2);
}
int main()
{
// freopen("1.in","r",stdin);
cin>>n; m=n; For(a,2,n)
{
int b; ll c; cin>>b>>c;
w[a].emplace_back(b,c),w[b].emplace_back(a,c);
} dfs0(1,0);
vector<int> leafs; vector<array<ll,3>> vx; vector<array<int,3>> vq;
For(i,1,n) if(w[i].size()==1) leafs.push_back(i);
int sz=leafs.size(); For(i,0,sz-1)
{
ll a=leafs[i],b=leafs[(i+1)%sz],c; cin>>c;
vx.push_back({a,b,c});
} cin>>q; For(i,1,q) {int a,b; cin>>a>>b; vq.push_back({a,b,i}),ans[i]=inf;}
n=m,rt=0,sum=n,maxs=n+5,GetRt(1,0),dfs(rt,vx,vq);
For(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 22260kb
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
9 8 0 9 9 8
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 22216kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 0 0 0 0 0 0 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
7 8 8 7 7 7 0 7 1 7 7 7 1 7 0 7 0 8 1 6 0
result:
ok 21 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 22472kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
9 8 8 15 9 14 0 7 1 7 14 9 15 9 22 9 23 8 15 16 16
result:
ok 21 numbers
Test #4:
score: -100
Wrong Answer
time: 704ms
memory: 66864kb
input:
99998 1 683940 1 335116 3 198362 4 28825 5 625394 6 314200 7 270653 8 61629 9 650997 10 693039 11 159577 12 466708 13 715788 14 262771 15 615302 16 1457 17 650381 18 542652 19 101993 20 197937 21 474452 22 859631 23 327526 24 705522 25 500710 26 595050 27 577264 28 955258 29 269967 30 4012 31 471435...
output:
683940 335116 533478 562303 1187697 1501897 1772550 1834179 2485176 3178215 3337792 3804500 4520288 4783059 5398361 5399818 6050199 6592851 6694844 6892781 7367233 8226864 8554390 9259912 9760622 10355672 10932936 11888194 12158161 12162173 12633608 13385421 13746582 14637654 14649654 15558759 15771...
result:
wrong answer 579th numbers differ - expected: '241644089', found: '241082347'