QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191887 | #7513. Palindromic Beads | ucup-team266# | WA | 474ms | 272156kb | C++14 | 4.3kb | 2023-09-30 12:16:52 | 2023-09-30 12:16:53 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
vector <int> g[200005];
struct LCA
{
int dep[200005],dfn[200005],times;
int st[20][400005],Lg[400005];
void dfs(int u,int fa)
{
dfn[u]=++times,st[0][times]=u;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
dep[v]=dep[u]+1,dfs(v,u);
st[0][++times]=u;
}
}
int mindep(int x,int y)
{
if(dep[x]<dep[y]) return x;
return y;
}
void build()
{
times=0,dep[1]=0;
dfs(1,-1);
Lg[1]=0,Lg[2]=1;
for(int i=3;i<=times;i++) Lg[i]=Lg[i/2]+1;
for(int k=1;k<20;k++) for(int i=1;i+(1<<k)-1<=times;i++)
st[k][i]=mindep(st[k-1][i],st[k-1][i+(1<<(k-1))]);
}
int getlca(int u,int v)
{
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v);
int s=Lg[v-u+1];
return mindep(st[s][u],st[s][v-(1<<s)+1]);
}
int getdist(int u,int v)
{
int lc=getlca(u,v);
return dep[u]+dep[v]-2*dep[lc];
}
}Lca;
int ls[40000005],rs[40000005],val[40000005],uidx;
void update(int id,int l,int r,int x,int d)
{
val[id]=max(val[id],d);
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid)
{
if(!ls[id]) ls[id]=++uidx;
update(ls[id],l,mid,x,d);
}
else
{
if(!rs[id]) rs[id]=++uidx;
update(rs[id],mid+1,r,x,d);
}
}
int query(int id,int l,int r,int x,int y)
{
if(!id) return 0;
if(x<=l&&r<=y) return val[id];
int mid=(l+r)>>1,res=0;
if(x<=mid) res=max(res,query(ls[id],l,mid,x,y));
if(y>mid) res=max(res,query(rs[id],mid+1,r,x,y));
return res;
}
int Rt[800005],n;
void update2d(int id,int l,int r,int x1,int x2,int d)
{
update(Rt[id],1,n,x2,d);
if(l==r) return;
int mid=(l+r)>>1;
if(x1<=mid) update2d(id<<1,l,mid,x1,x2,d);
else update2d(id<<1|1,mid+1,r,x1,x2,d);
}
int query2d(int id,int l,int r,int x1,int y1,int x2,int y2)
{
if(x1<=l&&r<=y1) return query(Rt[id],1,n,x2,y2);
int mid=(l+r)>>1,res=0;
if(x1<=mid) res=max(res,query2d(id<<1,l,mid,x1,y1,x2,y2));
else res=max(res,query2d(id<<1|1,mid+1,r,x1,y1,x2,y2));
return res;
}
vector <int> has[200005];
int c[200005];
int dfn[200005],R[200005],clk;
void dfs0(int u,int fa)
{
dfn[u]=R[u]=++clk;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
dfs0(v,u),R[u]=R[v];
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>c[i],has[c[i]].pb(i);
for(int i=1;i<=4*n;i++) Rt[i]=++uidx;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v),g[v].pb(u);
}
Lca.build();
vector <pii > vec;
for(int i=1;i<=n;i++) if(has[i].size()==2) vec.pb(mp(Lca.getdist(has[i][0],has[i][1]),i));
sort(vec.begin(),vec.end()),reverse(vec.begin(),vec.end());
int ans=1;
dfs0(1,-1);
for(int i=0;i<vec.size();i++)
{
int col=vec[i].se;
int u=has[col][0],v=has[col][1];
// cout<<u<<" "<<v<<"\n";
int dp=2;
if(dfn[u]>dfn[v]) swap(u,v);
if(dfn[u]<=dfn[v]&&dfn[v]<=R[u])
{
// cout<<"1.\n";
int u2=u;
for(int j=0;j<g[u].size();j++) if(Lca.getlca(v,g[u][j])==g[u][j]&&dfn[g[u][j]]>dfn[u]) u2=g[u][j];
if(dfn[u2]-1) dp=max(dp,query2d(1,1,n,dfn[v],R[v],1,dfn[u2]-1)+2),dp=max(dp,query2d(1,1,n,1,dfn[u2]-1,dfn[v],R[v])+2);
if(R[u2]+1<=n) dp=max(dp,query2d(1,1,n,dfn[v],R[v],R[u2]+1,n)+2),dp=max(dp,query2d(1,1,n,R[u2]+1,n,dfn[v],R[v])+2);
// cout<<"...\n";
}
else
{
// cout<<"2.\n";
dp=max(dp,query2d(1,1,n,dfn[u],R[u],dfn[v],R[v])+2);
dp=max(dp,query2d(1,1,n,dfn[v],R[v],dfn[u],R[u])+2);
// cout<<"...\n";
}
update2d(1,1,n,dfn[u],dfn[v],dp);
// update2d(1,1,n,dfn[v],dfn[u],dp);
if(Lca.getdist(u,v)!=1) dp++;
ans=max(ans,dp);
// cout<<"...\n";
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22644kb
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: 2ms
memory: 27880kb
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: 27328kb
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: 0
Accepted
time: 0ms
memory: 24592kb
input:
6 1 2 3 4 5 6 1 2 2 3 3 4 4 5 5 6
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 8ms
memory: 40500kb
input:
2000 845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...
output:
5
result:
ok single line: '5'
Test #6:
score: 0
Accepted
time: 428ms
memory: 272156kb
input:
200000 48015 47923 20609 71806 43752 68214 95683 89449 25809 58110 19878 52931 7845 45206 86245 82945 62977 37876 12456 105915 10509 92943 66950 88545 26442 26545 42278 66977 3970 9631 21524 43638 7979 58240 25719 56260 276 89721 9553 16550 52161 30307 82748 108443 36676 48581 59069 57412 62453 7965...
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 474ms
memory: 268236kb
input:
200000 13011 51198 65374 107045 66506 14385 35784 94265 71449 41817 24646 60714 53382 68358 9354 840 3139 71282 72215 69550 2121 41498 13675 76444 67690 40513 56439 12832 51976 35333 47208 59602 98993 9383 77866 10464 41517 89125 58804 91741 66160 74208 70991 63865 84870 14282 2441 78046 73372 36311...
output:
7
result:
ok single line: '7'
Test #8:
score: -100
Wrong Answer
time: 397ms
memory: 271180kb
input:
200000 38715 33241 65919 39407 27500 36200 2259 42301 79147 57505 20 81399 69499 23658 14534 86934 14352 69558 59763 43318 35360 3281 38188 40058 40571 103709 75625 8434 53802 87159 98628 69421 53711 47986 18350 6079 37362 39377 71936 89573 25983 66882 48999 58918 66432 17453 82515 9588 95375 87287 ...
output:
19
result:
wrong answer 1st lines differ - expected: '45', found: '19'