Submission #594458

#	Time	Username	Problem	Language	Result	Execution time	Memory
594458		qwerasdfzxcl	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	239 ms	17104 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[200200], st;
int n, m, c[200200], d[200200], h[200200], ans[200200], cnt[200200], dist[200200], cur;

void dfs0(int s, int pa = -1){
    if (pa!=-1) d[s] = d[pa] + 1;
    else d[s] = 1;
    h[s] = 1;
    for (auto &v:adj[s]) if (v!=pa){
        dfs0(v, s);
        h[s] = max(h[s], h[v]+1);
    }
}

void _insert(int s){
    if (st.empty() || st.back()!=s){
        st.push_back(s);
        if (!cnt[c[s]]) cur++;
        cnt[c[s]]++;
    }
}

void _pop(int s, int x){
    while(!st.empty() && d[s] - d[st.back()] <= x){
        --cnt[c[st.back()]];
        if (!cnt[c[st.back()]]) cur--;
        st.pop_back();
    }
}

void dfs(int s, int pa = -1){
    vector<int> deep;
    for (auto &v:adj[s]) if (v!=pa){
        deep.push_back(v);
        for (int i=(int)deep.size()-1;i;i--){
            if (h[deep[i-1]] >= h[deep[i]]) break;
            swap(deep[i-1], deep[i]);
        }
        if (deep.size()>2) deep.pop_back();
    }

    if (deep.size()<=1){
        _insert(s);

        for (auto &v:adj[s]) if (v!=pa) dfs(v, s);

        deep.push_back(0);
        _pop(s, h[deep[0]]);
        /*printf("%d: ", s);
        for (auto &x:st) printf("%d ", x);
        printf("\n");*/
        if (dist[s] < d[s]){
            ans[s] = cur;
            dist[s] = d[s];
        }
        return;
    }

    _pop(s, h[deep[1]]);
    _insert(s);

    dfs(deep[0], s);

    _pop(s, 0);
    /*printf("%d: ", s);
    for (auto &x:st) printf("%d ", x);
    printf("\n");*/
    if (dist[s] < d[s]){
        ans[s] = cur;
        dist[s] = d[s];
    }
    _insert(s);

    for (auto &v:adj[s]) if (v!=pa && v!=deep[0]){
        dfs(v, s);
        _insert(s);
    }
    _pop(s, 0);
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n-1;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i=1;i<=n;i++) scanf("%d", c+i);

    dfs0(1);
    int r1 = max_element(d+1, d+n+1) - d;
    dfs0(r1);
    dfs(r1);

    /*printf("r1 = %d\n", r1);
    for (int i=1;i<=n;i++) printf("%d\n", ans[i]);*/

    int r2 = max_element(d+1, d+n+1) - d;
    dfs0(r2);
    dfs(r2);

    //printf("r2 = %d\n", r2);
    for (int i=1;i<=n;i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:93:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     for (int i=1;i<=n;i++) scanf("%d", c+i);
      |                            ~~~~~^~~~~~~~~~~

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