QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300831 | #6101. Ring Road | PhantomThreshold | WA | 4125ms | 40044kb | C++20 | 4.0kb | 2024-01-08 21:25:04 | 2024-01-08 21:25:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin>>n;
vector<vector<int>> T(n+n+5);
vector<vector<pair<int,ll>>> tmp(n+n+5),G(n+n+5);
auto addedge=[&](int u,int v,ll w,int ty=1)
{
// cerr<<"addedge "<<u<<' '<<v<<' '<<w<<endl;
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
if(ty)
{
T[u].push_back(v);
T[v].push_back(u);
}
};
for(int i=2;i<=n;i++)
{
int p;
ll c;
cin>>p>>c;
tmp[p].emplace_back(i,c);
}
vector<int> lf;
int ind=n;
for(int i=1;i<=n;i++)
{
// cerr<<"split "<<i<<' '<<tmp[i].size()<<endl;
if(tmp[i].empty())lf.push_back(i);
else
{
int now=i;
while(tmp[i].size()>2u)
{
auto [v,w]=tmp[i].back();
tmp[i].pop_back();
addedge(now,v,w);
addedge(now,++ind,0);
now=ind;
}
addedge(now,tmp[i][0].first,tmp[i][0].second);
if(tmp[i].size()>1u)addedge(now,tmp[i][1].first,tmp[i][1].second);
}
}
n=ind;
int lcnt=(int)lf.size();
for(int i=0;i<lcnt;i++)
{
ll c;
cin>>c;
addedge(lf[i],lf[(i+1)%lcnt],c,0);
addedge(lf[(i+1)%lcnt],lf[i],c,0);
}
int q;
cin>>q;
vector<ll> ans(q+5,inf);
vector<tuple<int,int,int>> qu(q+5);
for(int i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
qu[i]=make_tuple(u,v,i);
}
vector<ll> dis(n+5,inf);
vector<int> good(n+5);
auto dijk=[&](int s,int fl)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
dis[s]=0;
pq.emplace(0,s);
while(not pq.empty())
{
auto [d,u]=pq.top();pq.pop();
if(dis[u]!=d)continue;
for(auto [v,w]:G[u])
{
if(good[v]==fl and dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
pq.emplace(dis[v],v);
}
}
}
};
auto deledge=[&](int u,int v)
{
// cerr<<"delete edge "<<u<<' '<<v<<endl;
for(auto it=G[u].begin();it!=G[u].end();++it)
{
if(it->first==v)
{
G[u].erase(it);
break;
}
}
for(auto it=G[v].begin();it!=G[v].end();++it)
{
if(it->first==u)
{
G[v].erase(it);
break;
}
}
};
dijk(lf[0],0);
for(auto [u,v,id]:qu)
{
ans[id]=min(ans[id],dis[u]+dis[v]);
}
deledge(lf[0],lf[lcnt-1]);
vector<int> used(n+5),siz(n+5),mxson(n+5),vis(n+5),bel(n+5);
vector<int> subs;
int gcnt=0;
function<void(int)> dfs0=[&](int u)
{
// cerr<<"dfs0 "<<u<<endl;
siz[u]=1;mxson[u]=0;
vis[u]=1;
subs.push_back(u);
for(auto v:T[u])
{
if(not used[v] and not vis[v])
{
dfs0(v);
siz[u]+=siz[v];
if(siz[v]>siz[mxson[u]])
mxson[u]=v;
}
}
};
function<void(int,int)> dfs1=[&](int r,int u)
{
siz[u]=1;mxson[u]=0;
vis[u]=0;
for(auto v:T[u])
{
if(not used[v] and vis[v])
{
if(u==r)bel[v]=v;
else bel[v]=bel[u];
dfs1(r,v);
siz[u]+=siz[v];
}
}
};
function<void(int,vector<tuple<int,int,int>>)> Divide=[&](int u,vector<tuple<int,int,int>> curq)
{
// cerr<<"Divide "<<u<<endl;
subs.clear();
dfs0(u);
int r=u,sz=siz[u];
while(mxson[r] and siz[mxson[r]]>=sz/2)
{
r=mxson[r];
}
// cerr<<"G="<<r<<endl;
dfs1(r,r);
++gcnt;
vector<pair<int,int>> sp;
for(auto x:subs)
{
// cerr<<x<<' '<<bel[x]<<endl;
good[x]=gcnt;
dis[x]=inf;
if(x==r)continue;
for(auto [y,w]:G[x])
{
if(x<y and bel[x]!=bel[y])
sp.emplace_back(x,y);
}
}
dijk(r,gcnt);
for(auto [a,b,c]:curq)
{
ans[c]=min(ans[c],dis[a]+dis[b]);
}
for(auto [x,y]:sp)
{
for(auto z:subs)
{
dis[z]=inf;
}
dijk(x,gcnt);
for(auto [a,b,c]:curq)
{
ans[c]=min(ans[c],dis[a]+dis[b]);
}
deledge(x,y);
}
used[u]=1;
for(auto v:T[u])
{
if(not used[v])
{
vector<tuple<int,int,int>> tmpq;
for(auto [a,b,c]:curq)
{
if(bel[a]==v and bel[b]==v)
tmpq.emplace_back(a,b,c);
}
Divide(v,tmpq);
}
}
};
Divide(1,qu);
for(int i=1;i<=q;i++)
cout<<ans[i]<<"\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 0ms
memory: 3456kb
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: 3512kb
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: 4125ms
memory: 40044kb
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 1702996 1901358 1930183 2555577 2869777 3140430 3202059 3853056 4546095 4705672 5172380 5888168 6150939 6766241 6767698 7418079 7960731 8062724 8260661 8735113 9594744 9922270 10627792 11128502 11723552 12300816 13256074 13526041 13530053 14001488 14753301 15114462 16005534 16017534 16926639 ...
result:
wrong answer 2nd numbers differ - expected: '335116', found: '1702996'