QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180706#7103. Red Black Treeucup-team870AC ✓1989ms38388kbC++144.1kb2023-09-16 10:36:062023-09-16 10:36:06

Judging History

你现在查看的是最新测评结果

  • [2023-09-16 10:36:06]
  • 评测
  • 测评结果:AC
  • 用时:1989ms
  • 内存:38388kb
  • [2023-09-16 10:36:06]
  • 提交

answer

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int read(){
	int x=0,fh=1; char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') fh=-1;
	for (;isdigit(ch);ch=getchar()) x=x*10+(ch^48);
	return x*fh;
}
const int N=1e5+5;
int dfn[N],dep[N];
struct node{
    int y,w;
};
vector<node> v[N];
void add(int x,int y,int z){
	v[x].push_back(node{y,z});
}
namespace LCA{
	int dfnn,lg2[N<<1],q[N<<1],pl[N],st[18][N<<1],cnt;
	void dfs(int x,int fa,int de){
		dfn[x]=++dfnn; //求dfs序和深度
		dep[x]=de; cnt++;
		if (!pl[x]) pl[x]=cnt; q[cnt]=x;
		for(auto i:v[x])
			if (i.y!=fa) dfs(i.y,x,de+1),q[++cnt]=x;
	}
	void init(int n,int root){
		For(i,2,n<<1) lg2[i]=lg2[i/2]+1;
        dfs(root,0,1);
        For(i,1,cnt) st[0][i]=q[i];
        For(i,1,lg2[cnt])
            For(j,1,cnt-(1<<i)+1){
				int l=st[i-1][j],r=st[i-1][j+(1<<i-1)];
                if (dep[l]<=dep[r]) st[i][j]=l;
                else st[i][j]=r;
			}
	}
	int lca(int x,int y){
		x=pl[x],y=pl[y];
		if (x>y) swap(x,y);
        int lg=lg2[y-x+1];
		int l=st[lg][x],r=st[lg][y-(1<<lg)+1];
        if (dep[l]<=dep[r]) return l;
        else return r;
	}
	void clear(int n){
		For(i,1,n) pl[i]=0,v[i].clear();
		cnt=0; dfnn=0;
	}
}
using LCA::lca;
int po[N],pl; //关键点
int red[N],d[N]; long long vw[N],dw[N];
void idfs(int x,int fa,int dd,long long y){
    vw[x]=y;
    if (red[x]) d[x]=x; else d[x]=dd;
    dw[x]=-vw[d[x]]+vw[x]; //cout<<"!!"<<vw[x]<<' '<<vw[d[x]]<<endl;
    for(auto i:v[x]) if (i.y!=fa){
        idfs(i.y,x,d[x],y+i.w);
    }
}
bool ppf[N]; int c[N];
namespace newtree{
	//vector<int> v[N<<1];
	int to[N<<1],nex[N<<1],head[N],e;
    int st[N<<1];
	bool cmd(int x,int y){
		return dfn[x]<dfn[y];
	}
	void add(int x,int y){
		//cout<<x<<' '<<y<<endl;
		//v[x].push_back(y);
        to[++e]=y; nex[e]=head[x]; head[x]=e;
	}
	int build(){
		//需要预处理dep, dfn和求lca
		e=0;
        sort(po+1,po+1+pl,cmd);
		int top=0;
For(i,1,pl-1){
			st[++top]=po[i]; st[++top]=lca(po[i],po[i+1]);
		}
		st[++top]=po[pl];
		sort(st+1,st+top+1,cmd);
		top=unique(st+1,st+top+1)-st-1;
		For(i,1,top-1){
			int lc=lca(st[i],st[i+1]);
			add(lc,st[i+1]);
		}
		return st[1]; //root
	}
    void clear(int x){
		for(int i=head[x];i;i=nex[i]) clear(to[i]);
		head[x]=0;
	}
    long long now[N],l,r,mid; int ocnt;
	bool dfs(int x,int fa){
        now[x]=0; c[x]=0;
        if (ppf[x]) ++c[x];
        bool redf;
        for(int i=head[x];i;i=nex[i]){
            int y=to[i];
            redf=dfs(y,x);
            if (!redf&&c[y])
                c[x]+=c[y],now[x]=max(now[x],now[y]-vw[x]+vw[y]);
        }
        if (red[x]) {c[x]=0; return 1;}
        else if (c[x]&&now[x]-vw[fa]+vw[x]>mid) {c[x]=0; ++ocnt; return 1;}
        else return 0;
    }
    void work(){
        int root=build();
        //dp
        l=0,r=0; r=r*r;
        For(i,1,pl) r=max(r,dw[po[i]]);
        while(l<r){
            mid=(l+r)>>1; ocnt=0;
            dfs(root,0);
            if (ocnt<=1) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l); //cout<<endl;
        clear(root);
    }
}
bool pf[N];
int main(){
    int _=read();
    while(_--){
        int n=read(),m=read(),k=read(),x,y,z;
        For(i,1,m) x=read(),red[x]=1;
        For(i,1,n-1) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
        LCA::init(n,1); //root记得改
        idfs(1,0,0,0);
        while(k--){
            //build
            pl=read();
            For(i,1,pl) po[i]=read(),ppf[po[i]]=pf[ po[i] ]=1;
            int tmp=pl;
            For(i,1,tmp) if (!pf[ d[po[i]] ]){
                pf[ d[po[i]] ]=1; po[++pl]=d[po[i]];
            }
            //cout<<"!!"<<pl<<endl;
            //For(i,1,pl) cout<<po[i]<<' '; cout<<endl;
            newtree::work();
            For(i,1,pl) ppf[po[i]]=pf[po[i]]=0;
        }
        LCA::clear(n);
        memset(red,0,(n+1)<<2);
    }
	return 0;
}
/*
10
1 2 1 5 1 9
2 3 2 4
5 6 5 7
7 8 7 10
2
4 2 9 7 8
3 4 6 10
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 18264kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 1989ms
memory: 38388kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed