QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#194739 | #7513. Palindromic Beads | ucup-team134# | WA | 2ms | 29988kb | C++14 | 3.6kb | 2023-09-30 22:02:39 | 2023-09-30 22:02:40 |
Judging History
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'