Submission #241074

#	Time	Username	Problem	Language	Result	Execution time	Memory
241074		arnold518	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	342 ms	24312 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, M, A[MAXN+10];
vector<int> adj[MAXN+10];

int P, Q;
int DP[MAXN+10], DQ[MAXN+10];

void dfs(int now, int bef, int *D, int dep)
{
    D[now]=dep;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, D, dep+1);
    }
}

int H[MAXN+10];
vector<int> chd[MAXN+10];

void dfs2(int now, int bef)
{
    H[now]=0;
    chd[now].clear();
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        chd[now].push_back(nxt);
        dfs2(nxt, now);
        H[now]=max(H[now], H[nxt]+1);
    }
    sort(chd[now].begin(), chd[now].end(), [&](const int &p, const int &q) { return H[p]>H[q]; });
}

int cnt[MAXN+10], chk[MAXN+10], ans[MAXN+10];
vector<pii> V;

void dfs3(int now, int bef, int dep)
{
    int i, j;
    if(chd[now].size()==0)
    {
        if(chk[now]) ans[now]=V.size();
        return;
    }
    else if(chd[now].size()==1)
    {
        if((V.empty() || V.back().first!=dep) && !cnt[A[now]]) V.push_back({dep, A[now]}), cnt[A[now]]++;
        dfs3(chd[now][0], now, dep+1);
        while(!V.empty() && V.back().first>=dep-H[now])
        {
            cnt[V.back().second]--;
            V.pop_back();
        }
        if(chk[now]) ans[now]=V.size();
        return;
    }
    else
    {
        while(!V.empty() && V.back().first>=dep-H[chd[now][1]]-1)
        {
            cnt[V.back().second]--;
            V.pop_back();
        }
        if((V.empty() || V.back().first!=dep) && !cnt[A[now]]) V.push_back({dep, A[now]}), cnt[A[now]]++;
        dfs3(chd[now][0], now, dep+1);
        while(!V.empty() && V.back().first>=dep-H[chd[now][0]]-1)
        {
            cnt[V.back().second]--;
            V.pop_back();
        }
        if((V.empty() || V.back().first!=dep) && !cnt[A[now]]) V.push_back({dep, A[now]}), cnt[A[now]]++;
        for(i=1; i<chd[now].size(); i++)
        {
            int nxt=chd[now][i];
            dfs3(nxt, now, dep+1);
        }
        while(!V.empty() && V.back().first>=dep-H[now])
        {
            cnt[V.back().second]--;
            V.pop_back();
        }
        if(chk[now]) ans[now]=V.size();
        return;
    }
}  

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<N; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(i=1; i<=N; i++) scanf("%d", &A[i]);

    dfs(1, 1, DP, 0); P=1;
    for(i=1; i<=N; i++) if(DP[P]<DP[i]) P=i;
    dfs(P, P, DP, 0); Q=1;
    for(i=1; i<=N; i++) if(DP[Q]<DP[i]) Q=i;
    dfs(Q, Q, DQ, 0);

    //printf("%d %d\n", P, Q);

    memset(chk, 0, sizeof(chk));
    memset(cnt, 0, sizeof(cnt));
    V.clear();
    for(i=1; i<=N; i++) if(DP[i]>DQ[i]) chk[i]=1;
    dfs2(P, P);
    dfs3(P, P, 0);

    memset(chk, 0, sizeof(chk));
    memset(cnt, 0, sizeof(cnt));
    V.clear();
    for(i=1; i<=N; i++) if(DP[i]<=DQ[i]) chk[i]=1;
    dfs2(Q, Q);
    dfs3(Q, Q, 0);    

    for(i=1; i<=N; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs3(int, int, int)':
joi2019_ho_t5.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<chd[now].size(); i++)
                  ~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:48:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:98:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
joi2019_ho_t5.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:108:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i]);
                         ~~~~~^~~~~~~~~~~~~

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