Submission #202129

#	Time	Username	Problem	Language	Result	Execution time	Memory
202129		gs18115	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	911 ms	45176 KiB

joi2019_ho_t5

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct seg
{
    int c[1000010],sm[1000010],t[1000010];
    seg(){}
    inline void init()
    {
        fill(c,c+1000010,0);
        fill(sm,sm+1000010,0);
        fill(t,t+1000010,0);
    }
    inline void set(int n)
    {
        t[n]=c[n]>0?sm[n]:(n<400005?t[n*2]+t[n*2+1]:0);
        return;
    }
    void set(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            sm[n]=p;
            set(n);
            return;
        }
        int m=(s+e)/2;
        if(x>m)
            set(n*2+1,m+1,e,x,p);
        else
            set(n*2,s,m,x,p);
        sm[n]=sm[n*2]+sm[n*2+1];
        set(n);
        return;
    }
    bool get(int n,int s,int e,int x)
    {
        if(c[n]>0)
            return 1;
        if(s==e)
            return 0;
        int m=(s+e)/2;
        if(x>m)
            return get(n*2+1,m+1,e,x);
        return get(n*2,s,m,x);
    }
    void si(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
        {
            c[n]+=p;
            set(n);
            return;
        }
        int m=(s+e)/2;
        si(n*2,s,m,S,E,p);
        si(n*2+1,m+1,e,S,E,p);
        set(n);
        return;
    }
    inline int sq()
    {
        return t[1];
    }
}st;
vector<int>adj[250010];
int dp[250010],dp2[250010];
int fd[250010],sd[250010];
bool ch[250010];
int pos[250010];
int n,m;
void dfs(int x,int p)
{
    ch[x]=dp[p]+1>dp[x];
    dp[x]=dp[p]+1;
    for(int&t:adj[x])
        if(t!=p)
            dfs(t,x);
    fd[x]=sd[x]=0;
    for(int&t:adj[x])
    {
        if(t==p)
            continue;
        if(fd[x]<dp2[t])
            sd[x]=fd[x],fd[x]=dp2[t];
        else if(sd[x]<dp2[t])
            sd[x]=dp2[t];
    }
    dp2[x]=fd[x]+1;
    return;
}
int ans[250010],c[250010];
int c2;
void dfs2(int x,int p)
{
    if(ch[x])
    {
        int up=max(1,dp[x]-fd[x]);
        if(up<dp[x])
            st.si(1,1,n,up,dp[x]-1,1);
        ans[x]=c2-st.sq();
        if(up<dp[x])
            st.si(1,1,n,up,dp[x]-1,-1);
    }
    for(int&t:adj[x])
    {
        if(t==p)
            continue;
        int up=max(1,dp[x]-(dp2[t]==fd[x]?sd[x]:fd[x]));
        if(up<dp[x])
            st.si(1,1,n,up,dp[x]-1,1);
        int pp=pos[c[x]];
        bool cn=0;
        if(pp==0||st.get(1,1,n,pp))
            pos[c[x]]=dp[x],cn=1,st.set(1,1,n,dp[x],1),c2++;
        dfs2(t,x);
        if(cn)
            pos[c[x]]=pp,st.set(1,1,n,dp[x],0),c2--;
        if(up<dp[x])
            st.si(1,1,n,up,dp[x]-1,-1);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    for(int i=0;i++<n;)
        cin>>c[i];
    dfs(1,0);
    int l1=max_element(dp+1,dp+n+1)-dp;
    dfs(l1,0);
    for(int i=0;i++<n;)
        ch[i]=1;
    dfs2(l1,0);
    int l2=max_element(dp+1,dp+n+1)-dp;
    for(int i=0;i++<n;)
        ch[i]=0;
    dfs(l2,0);
    dfs2(l2,0);
    for(int i=0;i++<n;)
        cout<<ans[i]<<'\n';
    cout.flush();
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32