oj.uz

Submission #594476

# Submission time Handle Problem Language Result Execution time Memory
594476 2022-07-12T13:43:56 Z qwerasdfzxcl Unique Cities (JOI19_ho_t5) C++14
0 / 100
 266 ms 14312 KB 
#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 update(int s){
    if (dist[s] < d[s]){
        dist[s] = d[s];
        ans[s] = cur;
    }
}

void dfs(int s, int pa = -1){
    vector<int> deep; ///max and second max
    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.empty()){update(s); return;}
    if (deep.size()==2) _pop(s, h[deep[1]]); ///pop second max

    _insert(s);
    dfs(deep[0], s); ///traverse max first
    _pop(s, h[deep[0]]); ///pop all
    _insert(s);

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

    _pop(s, 0);
    update(s);
}

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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Incorrect 6 ms 5148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 235 ms 11376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 14312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4948 KB Output is correct
2 Incorrect 6 ms 5148 KB Output isn't correct
3 Halted 0 ms 0 KB -