QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198268#7513. Palindromic Beadsucup-team1525WA 7ms32640kbC++173.5kb2023-10-03 11:43:142023-10-03 11:43:14

Judging History

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

  • [2024-03-27 16:34:54]
  • hack成功,自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功,自动添加数据
  • (/hack/583)
  • [2023-10-03 11:43:14]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:32640kb
  • [2023-10-03 11:43:14]
  • 提交

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'