QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850883 | #4408. 燃烧的呐球 | 275307894a# | 100 ✓ | 7319ms | 816468kb | C++14 | 6.3kb | 2025-01-10 12:34:48 | 2025-01-10 12:34:49 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=N*20+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,m,k;vector<int> S[N];
int bg[N],en[N],bh,siz[N];
void make(int x,int La){
bg[x]=++bh;siz[x]=1;
for(int i:S[x]) make(i,x),siz[x]+=siz[i];
en[x]=bh;
}
int cnt,fa[N],c[N],X[N],Y[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
const pii If=make_pair(INF,-1);
struct node{
pii a,b;
node operator +(const node &B)const{
pii mi=min(a,B.a),ms=If;
if(a.se^mi.se) ms=min(ms,a);else ms=min(ms,b);
if(B.a.se^mi.se) ms=min(ms,B.a);else ms=min(ms,B.b);
return (node){mi,ms};
}
node operator +(const int &B)const{
return (node){make_pair(a.fi+B,a.se),make_pair(b.fi+B,b.se)};
}
}w[N];
const node inf=(node){make_pair(INF,0),If};
vector<int> Q1[N],Q2[N];
node w1[N],w2[N],w3[N],w4[N];
void dfs(int x,int La){
w1[x]=w1[La];w2[x]=w2[La];
w3[x]=w4[x]=inf;
for(int i:Q1[x]){
w1[x]=w1[x]+(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),If};
w3[x]=w3[x]+(node){make_pair(-siz[X[i]]+siz[Y[i]],c[i]),If};
}
for(int i:Q2[x]){
w2[x]=w2[x]+(node){make_pair(siz[Y[i]]+siz[X[i]],c[i]),If};
w4[x]=w4[x]+(node){make_pair(-siz[Y[i]]+siz[X[i]],c[i]),If};
}
for(int i:S[x]) dfs(i,x),w3[x]=w3[x]+w3[i],w4[x]=w4[x]+w4[i];
for(int i:Q1[x]){
w[i]=w[i]+(w1[x]+-siz[X[i]]+siz[Y[i]]);
w[i]=w[i]+(w3[x]+siz[X[i]]+siz[Y[i]]);
}
for(int i:Q2[x]){
w[i]=w[i]+(w2[x]+-siz[Y[i]]+siz[X[i]]);
w[i]=w[i]+(w4[x]+siz[Y[i]]+siz[X[i]]);
}
}
int st[N],sh;
int r1[N],r2[N];
namespace PreT{
node f[M],g[M];int cnt,L[M],R[M];
void clr(){
for(int i=0;i<=cnt;i++) L[i]=R[i]=0,f[i]=g[i]=inf;
f[0]=g[0]=inf;cnt=0;
}
void cp(int &v){
f[++cnt]=f[v];L[cnt]=L[v];R[cnt]=R[v];g[cnt]=g[v];
v=cnt;
}
void add(int x,int y,node w,int &v,int l=1,int r=n){
cp(v);f[v]=f[v]+w;if(x<=l&&r<=y){g[v]=g[v]+w;return;}
int m=l+r>>1;x<=m&&(add(x,y,w,L[v],l,m),0);y>m&&(add(x,y,w,R[v],m+1,r),0);
}
node qry(int x,int y,int v,int l=1,int r=n){
if(x<=l&&r<=y) return f[v];int m=l+r>>1;
return (x<=m?qry(x,y,L[v],l,m):inf)+(y>m?qry(x,y,R[v],m+1,r):inf)+g[v];
}
}
int r3[N],r4[N];
namespace Tree{
node f[M],g[M];int cnt,L[M],R[M];
void clr(){
for(int i=0;i<=cnt;i++) L[i]=R[i]=0,f[i]=g[i]=inf;
f[0]=g[0]=inf;cnt=0;
}
void add(int x,int y,node w,int &v,int l=1,int r=n){
if(!v){
v=++cnt;f[v]=g[v]=inf;
}
f[v]=f[v]+w;
if(x<=l&&r<=y){
g[v]=g[v]+w;
return;
}
int m=l+r>>1;x<=m&&(add(x,y,w,L[v],l,m),0);y>m&&(add(x,y,w,R[v],m+1,r),0);
}
node qry(int x,int y,int v,int l=1,int r=n){
if(x<=l&&r<=y) return f[v];int m=l+r>>1;
return (x<=m?qry(x,y,L[v],l,m):inf)+(y>m?qry(x,y,R[v],m+1,r):inf)+g[v];
}
int merge(int x,int y,int l=1,int r=n){
if(!x||!y) return x+y;
f[x]=f[x]+f[y];g[x]=g[x]+g[y];
if(l==r) return x;
int m=l+r>>1;L[x]=merge(L[x],L[y],l,m);R[x]=merge(R[x],R[y],m+1,r);
return x;
}
}
void DP(int x,int La){
r1[x]=r1[La];r2[x]=r2[La];
r3[x]=r4[x]=0;
for(int i:Q1[x]){
PreT::add(bg[Y[i]],bg[Y[i]],(node){make_pair(siz[X[i]]-siz[Y[i]],c[i]),If},r1[x]);
PreT::add(bg[Y[i]],en[Y[i]],(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),If},r2[x]);
Tree::add(bg[Y[i]],bg[Y[i]],(node){make_pair(-siz[X[i]]-siz[Y[i]],c[i]),If},r3[x]);
// gdb(i,bg[Y[i]],-siz[X[i]]-siz[Y[i]]);
Tree::add(bg[Y[i]],en[Y[i]],(node){make_pair(-siz[X[i]]+siz[Y[i]],c[i]),If},r4[x]);
}
for(int i:Q1[x]){
/*for(int y=1;y<=sh;y++){
int j=st[y];
int res=(siz[X[j]]-siz[X[i]]);
if(bg[Y[j]]<=bg[Y[i]]&&bg[Y[i]]<=en[Y[j]]){
res+=siz[Y[j]]-siz[Y[i]];
// w[i]=w[i]+(node){make_pair(res,c[j]),If};
// w[j]=w[j]+(node){make_pair(res,c[i]),If};
}
else if(bg[Y[i]]<=bg[Y[j]]&&bg[Y[j]]<=en[Y[i]]){
res+=siz[Y[i]]-siz[Y[j]];
// w[i]=w[i]+(node){make_pair(res,c[j]),If};
// w[j]=w[j]+(node){make_pair(res,c[i]),If};
}
}*/
st[++sh]=i;
w[i]=w[i]+(PreT::qry(bg[Y[i]],en[Y[i]],r1[x])+-siz[X[i]]+siz[Y[i]]);
w[i]=w[i]+(PreT::qry(bg[Y[i]],bg[Y[i]],r2[x])+-siz[X[i]]+-siz[Y[i]]);
}
for(int i:S[x]) DP(i,x),r3[x]=Tree::merge(r3[x],r3[i]),r4[x]=Tree::merge(r4[x],r4[i]);
for(int i:Q1[x]){
w[i]=w[i]+(Tree::qry(bg[Y[i]],en[Y[i]],r3[x])+siz[X[i]]+siz[Y[i]]);
// gdb(bg[Y[i]],en[Y[i]],siz[X[i]]+siz[Y[i]],i);
w[i]=w[i]+(Tree::qry(bg[Y[i]],bg[Y[i]],r4[x])+siz[X[i]]+-siz[Y[i]]);
}
for(int i:Q1[x]) sh--;
}
void Solve(){
scanf("%d%d",&n,&m);
// if(m>1000) return;
for(int i=2;i<=n;i++){
int x;scanf("%d",&x);
S[x].push_back(i);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&X[i],&Y[i]);
Q1[X[i]].push_back(i),Q2[Y[i]].push_back(i);
}
make(1,0);
iota(fa+1,fa+m+1,1);
cnt=m;
ll ans=0;
while(cnt^1){
for(int i=1;i<=m;i++) c[i]=GF(i);
node res=inf;
for(int i=1;i<=m;i++) res=res+(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),make_pair(INF,0)};
for(int i=1;i<=m;i++) w[i]=res+siz[X[i]]+siz[Y[i]];
w1[0]=w2[0]=inf;dfs(1,0);
PreT::clr();Tree::clr();
DP(1,0);
gdb(w[2].a.fi,w[2].b.fi);
for(int i=1;i<=m;i++) w[GF(i)]=w[GF(i)]+w[i];
vector<tuple<int,int,int> > e;
for(int i=1;i<=m;i++) if(fa[i]==i){
// gdb(i,w[i].a.fi,w[i].a.se,w[i].b.fi,w[i].b.se);
for(pii s:{w[i].a,w[i].b}) if(s.se>0&&GF(s.se)^GF(i)){e.emplace_back(s.fi,s.se,i);break;}
}
sort(all(e));
for(auto [w,a,b]:e){
if(GF(a)^GF(b)) ans+=w,fa[GF(a)]=GF(b),cnt--;
}
}
printf("%lld\n",ans);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 12ms
memory: 112448kb
Test #2:
score: 10
Accepted
time: 23ms
memory: 117392kb
Test #3:
score: 10
Accepted
time: 27ms
memory: 115632kb
Test #4:
score: 10
Accepted
time: 15ms
memory: 115708kb
Test #5:
score: 10
Accepted
time: 25ms
memory: 116036kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 2030ms
memory: 281744kb
Test #7:
score: 10
Accepted
time: 1208ms
memory: 279124kb
Test #8:
score: 10
Accepted
time: 804ms
memory: 271116kb
Test #9:
score: 10
Accepted
time: 777ms
memory: 274964kb
Test #10:
score: 10
Accepted
time: 1130ms
memory: 278836kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 3372ms
memory: 386940kb
Test #12:
score: 10
Accepted
time: 2112ms
memory: 383664kb
Test #13:
score: 10
Accepted
time: 1581ms
memory: 367612kb
Test #14:
score: 10
Accepted
time: 1545ms
memory: 376176kb
Test #15:
score: 10
Accepted
time: 2072ms
memory: 377452kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 724ms
memory: 209116kb
Test #17:
score: 20
Accepted
time: 850ms
memory: 213320kb
Test #18:
score: 20
Accepted
time: 555ms
memory: 213208kb
Test #19:
score: 20
Accepted
time: 567ms
memory: 211232kb
Test #20:
score: 20
Accepted
time: 714ms
memory: 213148kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 7283ms
memory: 812036kb
Test #22:
score: 10
Accepted
time: 7280ms
memory: 812484kb
Test #23:
score: 10
Accepted
time: 7319ms
memory: 811960kb
Test #24:
score: 10
Accepted
time: 7229ms
memory: 812004kb
Test #25:
score: 10
Accepted
time: 7189ms
memory: 816468kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1501ms
memory: 520716kb
Test #27:
score: 10
Accepted
time: 1511ms
memory: 522932kb
Test #28:
score: 10
Accepted
time: 1512ms
memory: 518012kb
Test #29:
score: 10
Accepted
time: 1539ms
memory: 523588kb
Test #30:
score: 10
Accepted
time: 1577ms
memory: 523452kb
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: 5112ms
memory: 563992kb
Test #32:
score: 30
Accepted
time: 2986ms
memory: 555660kb
Test #33:
score: 30
Accepted
time: 2316ms
memory: 542260kb
Test #34:
score: 30
Accepted
time: 2317ms
memory: 550484kb
Test #35:
score: 30
Accepted
time: 2881ms
memory: 546936kb
Test #36:
score: 30
Accepted
time: 5180ms
memory: 568632kb
Test #37:
score: 30
Accepted
time: 3011ms
memory: 550492kb
Test #38:
score: 30
Accepted
time: 2341ms
memory: 538140kb
Test #39:
score: 30
Accepted
time: 2350ms
memory: 541340kb
Test #40:
score: 30
Accepted
time: 2915ms
memory: 547976kb