QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198268 | #7513. Palindromic Beads | ucup-team1525 | WA | 7ms | 32640kb | C++17 | 3.5kb | 2023-10-03 11:43:14 | 2023-10-03 11:43:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n;
int col[N+5],mc[N+5];
int lst[N+5];
vector<int> e[N+5];
namespace Segtr{
vector<int> tr[N*4+5];
#define lc id<<1
#define rc id<<1|1
void build(int l,int r,int id){
tr[id].clear();
tr[id].shrink_to_fit();
if(l==r) return;
int mid=l+r>>1;
build(l,mid,lc); build(mid+1,r,rc);
}
void insert(int l,int r,int st,int en,int x,int id){
// fprintf(stderr,"%d %d %d %d\n",l,r,st,en);
// if(en<l||st>r) while(1);
// while(1)
if(st<=l&&en>=r){
if(!tr[id].size()||x>=tr[id].back())
tr[id].push_back(x);
return;
}
int mid=l+r>>1;
if(st<=mid) insert(l,mid,st,en,x,lc);
if(en>mid) insert(mid+1,r,st,en,x,rc);
}
void getback(int l,int r,int st,int en,int x,int id){
if(st<=l&&en>=r){
if(tr[id].size()&&tr[id].back()==x) tr[id].pop_back();
return;
}
int mid=l+r>>1;
if(st<=mid) getback(l,mid,st,en,x,lc);
if(en>mid) getback(mid+1,r,st,en,x,rc);
}
int query(int l,int r,int p,int id){
int ans=0;
if(tr[id].size()) ans=tr[id].back();
if(l==r) return ans;
int mid=l+r>>1;
if(p<=mid) ans=max(ans,query(l,mid,p,lc));
else ans=max(ans,query(mid+1,r,p,rc));
return ans;
}
}
using namespace Segtr;
int ans;
bool used[N+5];
int fv[N+5],fu[N+5];
int sz[N+5],son[N+5];
void dfs1(int u,int tf){
sz[u]=1; son[u]=0;
for(auto v:e[u]){
if(v!=tf&&!used[v]){
dfs1(v,u);
if(sz[v]>sz[son[u]])
son[u]=v;
sz[u]+=sz[v];
}
}
}
int dfn[N+5],dfns;
void dfs2(int u,int tf,int tv,int tu){
fu[u]=tu; fv[u]=tv;
sz[u]=1;
dfn[u]=++dfns;
for(auto v:e[u])
if(!used[v]&&v!=tf){
dfs2(v,u,!tv?v:tv,tu);
sz[u]+=sz[v];
}
}
void dfs4(int u,int tf){
int res=0;
if(mc[u]){
int v=mc[u];
if(fv[v]!=fv[u]&&fu[v]==fu[u]){
res=query(1,dfns,dfn[v],1)+2;
// fprintf(stderr,"%d %d %d %d\n",1,dfns,dfn[v],dfn[v]+sz[v]-1);
// for(int i=1,j=0;i<=1000000000;i++) j++;
insert(1,dfns,dfn[v],dfn[v]+sz[v]-1,res,1);
ans=max(ans,res);
}
}
for(auto v:e[u])
if(!used[v]&&v!=tf) dfs4(v,u);
if(mc[u]){
int v=mc[u];
if(fv[v]!=fv[u]&&fu[u]==fu[v])
getback(1,dfns,dfn[v],dfn[v]+sz[v]-1,res,1);
}
}
void solve(int u){
dfs1(u,0);
int tot=sz[u];
while(sz[son[u]]*2>tot) u=son[u];
dfns=0;
dfs2(u,0,0,u);
build(1,dfns,1);
insert(1,dfns,1,dfns,1,1);
int delv=0;
if(mc[u]&&fu[mc[u]]==u){
int v=mc[u];
delv=fv[v];
insert(1,dfns,dfn[v],dfn[v]+sz[v]-1,2+(fv[v]!=v),1);
}
for(auto v:e[u])
if(!used[v]&&v!=delv) dfs4(v,u);
used[u]=1;
for(auto v:e[u])
if(!used[v]) solve(v);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&col[i]);
if(lst[col[i]]){
int j=lst[col[i]];
mc[i]=j; mc[j]=i;
}
lst[col[i]]=i;
}
for(int i=1,u,v;i<n;i++){
scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
ans=1;
solve(1);
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 32636kb
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: 7ms
memory: 32640kb
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: -100
Wrong Answer
time: 2ms
memory: 30404kb
input:
6 1 1 2 2 3 3 1 2 2 3 3 4 4 5 5 6
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'