QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505049 | #4408. 燃烧的呐球 | gxy001 | 100 ✓ | 2533ms | 357724kb | C++23 | 6.0kb | 2024-08-04 18:46:33 | 2024-08-04 18:46:34 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#define BUFSIZE 10000000
struct read{
char buf[BUFSIZE],*p1,*p2,c;
read():p1(buf),p2(buf){}
char gc(void){
return p1==p2?(std::cin.read(p1=buf,BUFSIZE),p2=p1+std::cin.gcount(),p1==p2?EOF:*p1++):*p1++;
}
read& operator >>(int& x){
c=gc(),x=0;
for(;c<'0'||c>'9';c=gc());
for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
return *this;
}
}cin;
using std::cout;
std::vector<int> v[1000010],x,y;
std::vector<std::pair<int,int>> t[1000010],h[1000010];
std::vector<std::pair<int,int>>*g;
int n,m,a[100010],b[100010],sz[1000010],xl[1000010],xr[1000010],yl[1000010],yr[1000010];
int f[100010],pcnt,col[100010],cs,*L,*R;
int find(int x){
while(x!=f[x]) x=f[x]=f[f[x]];
return x;
}
int rk[1000010];
int p[2000010],cct;
void dfs(int x){
static int cnt=0;
rk[x]=++cnt,sz[x]=1,p[++cct]=x;
for(auto u:v[x]) dfs(u),sz[x]+=sz[u];
p[++cct]=-x;
}
int const inf=1e9;
struct pnt{
int mn,mnt;
pnt():mn(inf),mnt(){}
pnt(int x,int y):mn(x),mnt(y){}
friend bool operator <(pnt const &a,pnt const &b){
return a.mn<b.mn;
}
pnt operator -(int x)const{
return pnt(mn-x,mnt);
}
pnt operator +(int x)const{
return pnt(mn+x,mnt);
}
}res[100010];
struct node{
pnt m,xm;
node():m(),xm(){}
node(pnt const &x):m(x),xm(){}
node(int x,int y):m(x,y),xm(){}
node(pnt const &x,pnt const &y):m(x),xm(y){}
void operator +=(node const &y){
if(y.m<m) xm=std::min(y.xm,col[m.mnt]==col[y.m.mnt]?xm:m),m=y.m;
else xm=std::min(xm,col[y.m.mnt]==col[m.mnt]?y.xm:y.m);
}
pnt query(int x)const{
if(col[m.mnt]==col[x]) return xm;
else return m;
}
};
namespace sub1{
node f[1000010],r[1000010];
void work(){
f[1]=node();
for(int i=1;i<=cct;i++){
int x=p[i];
if(x<0){
x=-x;
for(auto u:v[x]) r[x]+=r[u];
for(auto [i,u]:g[x]) res[i]=std::min(res[i],std::min(r[x].query(i)+sz[x]+sz[u],f[x].query(i)-sz[x]+sz[u]));
}else{
r[x]=node();
for(auto [i,u]:g[x]) f[x]+=node(sz[x]+sz[u],i),r[x]+=node(-sz[x]+sz[u],i);
for(auto u:v[x]) f[u]=f[x];
}
}
}
}
node tr[1800010];
namespace sub2{
int cnt,ls[1800010],rs[1800010],rt[1000010];
void update(int p,node const &v,int &x,int l=1,int r=cs){
if(!x) x=++cnt,ls[x]=rs[x]=0;
tr[x]+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(p<=mid) update(p,v,ls[x],l,mid);
else update(p,v,rs[x],mid+1,r);
}
void merge(int &x,int y){
if(!x||!y) return x|=y,void();
tr[x]+=tr[y];
merge(ls[x],ls[y]),merge(rs[x],rs[y]);
}
pnt query(int pl,int pr,int i,int x,int l=1,int r=cs){
if(l==pl&&r==pr) return tr[x].query(i);
int mid=(l+r)>>1;
if(pr<=mid) return query(pl,pr,i,ls[x],l,mid);
else if(pl>mid) return query(pl,pr,i,rs[x],mid+1,r);
else return std::min(query(pl,mid,i,ls[x],l,mid),query(mid+1,pr,i,rs[x],mid+1,r));
}
void work(){
for(int i=1;i<=cct;i++){
int x=p[i];
if(x<0){
x=-x;
rt[x]=0;
for(auto u:v[x]) merge(rt[x],rt[u]);
for(auto [i,u]:g[x]) update(L[u],node(-sz[x]-sz[u],i),rt[x]);
for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],R[u],i,rt[x])+sz[x]+sz[u]);
}
}
for(int i=1;i<=cnt;i++) tr[i]=node();
cnt=0;
}
}
int M;
int tp,s[3600010],top[1000010];
node val[3600010];
namespace sub3{
void update(int p,node const &v){
for(p+=M;p;p>>=1) ++tp,s[tp]=p,val[tp]=tr[p],tr[p]+=v;
}
pnt query(int x,int y,int i){
pnt ans;
for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1){
if(~x&1) ans=std::min(ans,tr[x^1].query(i));
if(y&1) ans=std::min(ans,tr[y^1].query(i));
}
return ans;
}
void work(){
M=1;
while(M<cs) M<<=1;
for(int i=1;i<=cct;i++){
int x=p[i];
if(x<0){
x=-x;
while(tp!=top[x]) tr[s[tp]]=val[tp],--tp;
}else{
top[x]=tp;
for(auto [i,u]:g[x]) update(L[u],node(sz[x]-sz[u],i));
for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],R[u],i)-sz[x]+sz[u]);
}
}
}
}
namespace sub4{
void update(int x,int y,node const &v){
for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1){
if(~x&1) ++tp,s[tp]=x^1,val[tp]=tr[x^1],tr[x^1]+=v;
if(y&1) ++tp,s[tp]=y^1,val[tp]=tr[y^1],tr[y^1]+=v;
}
}
pnt query(int p,int i){
pnt ans;
for(p+=M;p;p>>=1) ans=std::min(ans,tr[p].query(i));
return ans;
}
void work(){
M=1;
while(M<cs) M<<=1;
for(int i=1;i<=cct;i++){
int x=p[i];
if(x<0){
x=-x;
while(tp!=top[x]) tr[s[tp]]=val[tp],--tp;
}else{
top[x]=tp;
for(auto [i,u]:g[x]) update(L[u],R[u],node(sz[x]+sz[u],i));
for(auto [i,u]:g[x]) res[i]=std::min(res[i],query(L[u],i)-sz[x]-sz[u]);
}
}
}
}
int main(){
std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
cin>>n>>m;
for(int i=1,x;i<n;i++) cin>>x,v[x].push_back(i+1);
dfs(1);
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i],t[a[i]].emplace_back(i,b[i]),h[b[i]].emplace_back(i,a[i]),f[i]=i;
x.push_back(rk[b[i]]),y.push_back(rk[a[i]]);
}
std::sort(x.begin(),x.end());
std::sort(y.begin(),y.end());
x.resize(std::unique(x.begin(),x.end())-x.begin());
y.resize(std::unique(y.begin(),y.end())-y.begin());
for(int i=1;i<=m;i++)
xl[b[i]]=std::lower_bound(x.begin(),x.end(),rk[b[i]])-x.begin()+1,xr[b[i]]=std::upper_bound(x.begin(),x.end(),rk[b[i]]+sz[b[i]]-1)-x.begin(),
yl[a[i]]=std::lower_bound(y.begin(),y.end(),rk[a[i]])-y.begin()+1,yr[a[i]]=std::upper_bound(y.begin(),y.end(),rk[a[i]]+sz[a[i]]-1)-y.begin();
pcnt=m;
long long ans=0;
while(pcnt>1){
for(int i=1;i<=m;i++) col[i]=find(i);
node tt;
for(int i=1;i<=m;i++) tt+=node(sz[a[i]]+sz[b[i]],i);
for(int i=1;i<=m;i++) res[i]=tt.query(i)+sz[a[i]]+sz[b[i]];
g=t,cs=x.size(),L=xl,R=xr;
sub1::work();
sub2::work();
sub3::work();
sub4::work();
g=h,cs=y.size(),L=yl,R=yr;
sub1::work();
sub3::work();
static pnt link[100010];
static int c[100010];
for(int i=1;i<=m;i++) link[i]=pnt(),c[i]=0;
for(int i=1;i<=m;i++) if(res[i]<link[col[i]]) link[col[i]]=res[i],c[col[i]]=i;
for(int i=1;i<=m;i++) if(col[i]==i){
int u=find(link[i].mnt),v=find(c[i]);
if(u!=v) f[u]=v,ans+=link[i].mn,--pcnt;
}
}
cout<<ans<<'\n';
return 0;
}
Details
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 8ms
memory: 149256kb
Test #2:
score: 10
Accepted
time: 12ms
memory: 149320kb
Test #3:
score: 10
Accepted
time: 4ms
memory: 149060kb
Test #4:
score: 10
Accepted
time: 16ms
memory: 154612kb
Test #5:
score: 10
Accepted
time: 15ms
memory: 156780kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1107ms
memory: 269392kb
Test #7:
score: 10
Accepted
time: 674ms
memory: 265092kb
Test #8:
score: 10
Accepted
time: 434ms
memory: 259200kb
Test #9:
score: 10
Accepted
time: 464ms
memory: 263228kb
Test #10:
score: 10
Accepted
time: 637ms
memory: 262540kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 1698ms
memory: 276740kb
Test #12:
score: 10
Accepted
time: 1174ms
memory: 274864kb
Test #13:
score: 10
Accepted
time: 813ms
memory: 266560kb
Test #14:
score: 10
Accepted
time: 849ms
memory: 273672kb
Test #15:
score: 10
Accepted
time: 1097ms
memory: 271992kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 126ms
memory: 154188kb
Test #17:
score: 20
Accepted
time: 148ms
memory: 160076kb
Test #18:
score: 20
Accepted
time: 113ms
memory: 156216kb
Test #19:
score: 20
Accepted
time: 125ms
memory: 159820kb
Test #20:
score: 20
Accepted
time: 156ms
memory: 150292kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 2487ms
memory: 357720kb
Test #22:
score: 10
Accepted
time: 2481ms
memory: 357724kb
Test #23:
score: 10
Accepted
time: 2490ms
memory: 357144kb
Test #24:
score: 10
Accepted
time: 2533ms
memory: 355556kb
Test #25:
score: 10
Accepted
time: 2481ms
memory: 355024kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 687ms
memory: 238804kb
Test #27:
score: 10
Accepted
time: 684ms
memory: 241864kb
Test #28:
score: 10
Accepted
time: 698ms
memory: 242260kb
Test #29:
score: 10
Accepted
time: 691ms
memory: 240620kb
Test #30:
score: 10
Accepted
time: 684ms
memory: 240684kb
Subtask #7:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #31:
score: 30
Accepted
time: 2320ms
memory: 283444kb
Test #32:
score: 30
Accepted
time: 1520ms
memory: 282484kb
Test #33:
score: 30
Accepted
time: 1123ms
memory: 276100kb
Test #34:
score: 30
Accepted
time: 1197ms
memory: 281020kb
Test #35:
score: 30
Accepted
time: 1462ms
memory: 280232kb
Test #36:
score: 30
Accepted
time: 2332ms
memory: 284140kb
Test #37:
score: 30
Accepted
time: 1495ms
memory: 282172kb
Test #38:
score: 30
Accepted
time: 1133ms
memory: 276140kb
Test #39:
score: 30
Accepted
time: 1144ms
memory: 280804kb
Test #40:
score: 30
Accepted
time: 1448ms
memory: 280048kb