oj.uz

답안 #202116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202116 2020-02-14T00:17:48 Z gs18115 Unique Cities (JOI19_ho_t5) C++14
0 / 100
 1072 ms 49704 KB 
#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[800010],sm[800010],t[800010];
    seg()
    {
        fill(c,c+800010,0);
        fill(sm,sm+800010,0);
        fill(t,t+800010,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[200010];
int dp[200010],dp2[200010];
int fd[200010],sd[200010];
bool ch[200010];
int pos[200010];
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;
    dp2[x]=1;
    for(int&t:adj[x])
    {
        if(t==p)
            continue;
        dp2[x]=max(dp2[x],dp2[t]+1);
        if(fd[x]<dp2[t])
            sd[x]=fd[x],fd[x]=dp2[t];
        else if(sd[x]<dp2[t])
            sd[x]=dp2[t];
    }
    return;
}
int ans[200010],c[200010];
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);
    }
    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++;
    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);
        dfs2(t,x);
        if(up<dp[x])
            st.si(1,1,n,up,dp[x]-1,-1);
    }
    if(cn)
        pos[c[x]]=pp,st.set(1,1,n,dp[x],0),c2--;
    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);
    int l2=max_element(dp+1,dp+n+1)-dp;
    for(int i=0;i++<n;)
        ch[i]=0,dp[i]=dp2[i]=0;
    dfs(l1,0);
    dfs2(l1,0);
    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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 16 ms 14584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 421 ms 21172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 652 ms 24404 KB Output is correct
2 Correct 1002 ms 48032 KB Output is correct
3 Correct 99 ms 18296 KB Output is correct
4 Correct 903 ms 26924 KB Output is correct
5 Correct 1072 ms 49704 KB Output is correct
6 Correct 1000 ms 38160 KB Output is correct
7 Correct 871 ms 27008 KB Output is correct
8 Correct 941 ms 31572 KB Output is correct
9 Correct 1004 ms 29944 KB Output is correct
10 Correct 836 ms 29432 KB Output is correct
11 Execution timed out 47 ms 18552 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 16 ms 14584 KB Output isn't correct
3 Halted 0 ms 0 KB -