Submission #120152

#	Time	Username	Problem	Language	Result	Execution time	Memory
120152		Just_Solve_The_Problem	Unique Cities (JOI19_ho_t5)	C++11	100 / 100	715 ms	49252 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

#define ll long long
#define ok puts("OK");

using namespace std;

const int N = (int)2e5 + 7;

int n, m, A, B;
vector <int> gr[N];
int c[N], h[N], mxhe[N], cnt[N], ans[N];
vector <int> st;

int dfs1(int v, int pr) {
  int big = v;
  for (int to : gr[v]) {
    if (to == pr) continue;
    h[to] = h[v] + 1;
    int temp = dfs1(to, v);
    if (big == -1 || h[temp] > h[big]) {
      big = temp;
    }
  }
  return big;
}

int res;

void add(int x) {
  res += (cnt[x]++ == 0);
}

void del(int x) {
  res -= (--cnt[x] == 0);
}

void predfs(int v, int pr = 0) {
  mxhe[v] = h[v];
  for (int to : gr[v]) {
    if (to == pr) continue;
    h[to] = h[v] + 1;
    predfs(to, v);
    mxhe[v] = max(mxhe[v], mxhe[to]);
  }
}

void dfs(int v, int pr) {
  sort(gr[v].begin(), gr[v].end(), [&](const int &a1, const int &b1) {
    if (pr == b1) return true;
    if (pr == a1) return false;
    return mxhe[a1] > mxhe[b1];
  });
  vector <int> vec;
  for (int to : gr[v]) {
    if (to == pr) continue;
    vec.push_back(mxhe[to]);
  }
  int cnt = 0;
  for (int to : gr[v]) {
    if (to == pr) continue;
    if (!cnt && vec.size() > 1) {
      while (!st.empty() && abs(h[v] - h[st.back()]) <= vec[1] - h[v]) {
        del(c[st.back()]);
        st.pop_back();
      }
    } 
    add(c[v]);
    st.push_back(v);
    dfs(to, v);
    while (!st.empty() && abs(h[v] - h[st.back()]) <= vec[0] - h[v]) {
      del(c[st.back()]);
      st.pop_back();
    }
    cnt++;
  }
  ans[v] = max(ans[v], res);
}

main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
  }
  h[1] = 0;
  A = dfs1(1, 1);
  h[A] = 0;
  B = dfs1(A, A);
  h[A] = 0;
  predfs(A, A);
  dfs(A, A);
  /*for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << endl;
  return 0;
  */
  while (!st.empty()) {
    del(c[st.back()]);
    st.pop_back();
  }
  h[B] = 0; predfs(B, B);
  dfs(B, B);
  for (int i = 1; i <= n; i++) {
    printf("%d\n", ans[i]);
  }
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 2 4
5 4
1 2
2 3
3 4
3 5
1 2 3 4 5

*/

Compilation message (stderr)

joi2019_ho_t5.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:81:8: 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:84:10: 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:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c[i]);
     ~~~~~^~~~~~~~~~~~~

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