QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#300845 | #6101. Ring Road | PhantomThreshold | WA | 229ms | 46296kb | C++20 | 4.2kb | 2024-01-08 21:50:00 | 2024-01-08 21:50:00 |
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);
}
// cerr<<"read graph end"<<endl;
int q;
cin>>q;
vector<ll> ans(q+5,inf);
vector<tuple<int,int,int>> qu;
for(int i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
qu.emplace_back(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];
// cerr<<"go "<<r<<' '<<siz[r]<<' '<<mxson[r]<<' '<<siz[mxson[r]]<<endl;
while(mxson[r] and siz[mxson[r]]>=(sz+1)/2)
{
r=mxson[r];
}
// cerr<<"G="<<r<<endl;
bel[r]=0;
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]);
// cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
}
for(auto [x,y]:sp)
{
for(auto z:subs)
{
dis[z]=inf;
}
dijk(x,gcnt);
for(auto [a,b,c]:curq)
{
// cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
ans[c]=min(ans[c],dis[a]+dis[b]);
}
deledge(x,y);
}
used[r]=1;
for(auto v:T[r])
{
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: 0ms
memory: 3840kb
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: 3624kb
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: 3608kb
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: 0
Accepted
time: 229ms
memory: 46148kb
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:
ok 250000 numbers
Test #5:
score: -100
Wrong Answer
time: 127ms
memory: 46296kb
input:
99998 1 479670338308 2 121499701200 3 858712975908 4 144714509693 5 285977224040 6 864876191776 7 68574926716 8 310308615852 9 502806496434 10 361482163495 11 765497528076 12 895859015474 13 334706003457 14 379981526252 15 36757813515 16 157157422672 17 349512227463 18 338990361716 19 163391039440 2...
output:
479670338308 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000...
result:
wrong answer 2nd numbers differ - expected: '601170039508', found: '1000000000000000000'