QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194739#7513. Palindromic Beadsucup-team134#WA 2ms29988kbC++143.6kb2023-09-30 22:02:392023-09-30 22:02:40

Judging History

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

  • [2024-03-27 16:34:54]
  • hack成功,自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功,自动添加数据
  • (/hack/583)
  • [2023-09-30 22:02:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:29988kb
  • [2023-09-30 22:02:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=200050;
const int L=20;
int c[N];
vector<int> nodes[N];
vector<int> E[N];
int lid[N],rid[N],tid,par[N][L],dep[N];
void DFS(int u,int p){
	lid[u]=++tid;
	dep[u]=dep[p]+1;
	par[u][0]=p;
	for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
	for(int v:E[u]){
		if(v!=p){
			DFS(v,u);
		}
	}
	rid[u]=tid;
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=L-1;~i;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
	for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
int Dist(int u,int v){
	return dep[u]+dep[v]-2*dep[LCA(u,v)];
}

const int H=2*N;
const int M=2*N*L+H;
int ls[M],rs[M],tsz,root,rt[H],mx[M];
vector<int> vals[H];

void Set1(int&c,int ss,int se,int qi,int x){
	if(!c)c=++tsz;
	mx[c]=max(mx[c],x);
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Set1(ls[c],ss,mid,qi,x);
	else Set1(rs[c],mid+1,se,qi,x);
}

int Get1(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return mx[c];
	int mid=ss+se>>1;
	return max(Get1(ls[c],ss,mid,qs,qe),Get1(rs[c],mid+1,se,qs,qe));
}

void Build(int &c,int ss,int se){
	c=++tsz;
	if(ss==se)return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}

void Add(int c,int ss,int se,int qi,int x){
	vals[c].pb(x);
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Add(ls[c],ss,mid,qi,x);
	else Add(rs[c],mid+1,se,qi,x);
}

void Set2(int c,int ss,int se,int qi,int x,int val){
	int i=lower_bound(vals[c].begin(),vals[c].end(),x)-vals[c].begin()+1;
	Set1(rt[c],1,vals[c].size(),i,val);
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Set2(ls[c],ss,mid,qi,x,val);
	else Set2(rs[c],mid+1,se,qi,x,val);
}

int Get2(int c,int ss,int se,int qs,int qe,int L,int R){
	if(qs>qe||ss>qe||qs>se)return 0;
	if(qs<=ss&&qe>=se){
		int l=lower_bound(vals[c].begin(),vals[c].end(),L)-vals[c].begin()+1;
		int r=upper_bound(vals[c].begin(),vals[c].end(),R)-vals[c].begin();
		return Get1(rt[c],1,vals[c].size(),l,r);
	}
	int mid=ss+se>>1;
	return max(Get2(ls[c],ss,mid,qs,qe,L,R),Get2(rs[c],mid+1,se,qs,qe,L,R));
}

int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		scanf("%i",&c[i]);
		nodes[c[i]].pb(i);
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%i %i",&u,&v);
		E[u].pb(v);
		E[v].pb(u);
	}
	Build(root,1,n);
	DFS(1,0);
	vector<array<int,3>> work;
	for(int i=1;i<=n;i++){
		if(nodes[i].size()==2){
			int a=lid[nodes[i][0]];
			int b=lid[nodes[i][1]];
			if(a>b){
				swap(nodes[i][0],nodes[i][1]);
				swap(a,b);
			}
			Add(root,1,n,a,b);
			work.pb({Dist(nodes[i][0],nodes[i][1]),nodes[i][0],nodes[i][1]});
		}
	}
	for(int i=1;i<=tsz;i++){
		sort(vals[i].begin(),vals[i].end());
		vals[i].erase(unique(vals[i].begin(),vals[i].end()),vals[i].end());
	}
	sort(work.rbegin(),work.rend());
	int ans=0;
	for(auto path:work){
		int d=path[0];
		int a=path[1];
		int b=path[2];
		//printf("Work %i %i dist %i %i %i\n",a,b,d,Dist(a,b),LCA(a,b));

		int best=0;
		if(rid[a]>=lid[b]){
			int c=b;
			for(int i=L-1;~i;i--)if(dep[par[c][i]]>dep[a])c=par[c][i];
			best=max(Get2(root,1,n,1,lid[c]-1,lid[b],rid[b]),
					 Get2(root,1,n,lid[b],rid[b],rid[c]+1,n));
		}else{
			//printf("Get %i %i %i %i\n",lid[a],rid[a],lid[b],rid[b]);
			best=Get2(root,1,n,lid[a],rid[a],lid[b],rid[b]);
		}
		best+=2;
		Set2(root,1,n,lid[a],lid[b],best);
		//printf("Set %i %i %i\n",lid[a],lid[b],best);
		if(d>1)ans=max(ans,best+1);
		else ans=max(ans,best);
	}
	printf("%i\n",ans);
	return 0;
}

详细

Test #1:

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

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 26380kb

input:

5
1 3 2 2 1
1 2
2 3
3 4
4 5

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 28248kb

input:

6
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 26496kb

input:

6
1 2 3 4 5 6
1 2
2 3
3 4
4 5
5 6

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'