Submission #128295

#	Time	Username	Problem	Language	Result	Execution time	Memory
128295		IOrtroiii	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	854 ms	46200 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

vector<int> g[N];
int color[N];
int ans[N];
int dep[N], down[N];

void dfs(int u, int p) {
   for (int v : g[u]) {
      if (v != p) {
         dep[v] = dep[u] + 1;
         dfs(v, u);
      }
   }
}

void dfsDown(int u, int p) {
   down[u] = 0;
   for (int v : g[u]) {
      if (v != p) {
         dfsDown(v, u);
         down[u] = max(down[u], down[v] + 1);
      }
   }
}

struct {
   int stSz;
   int st[N];
   int cnt[N];
   int curAns;
   bool empty() {
      return stSz == 0;
   }
   int top() {
      return st[stSz - 1];
   }
   void push(int u) {
      if (++cnt[color[u]] == 1) {
         ++curAns;
      }
      st[stSz++] = u;
   }
   void pop() {
      int u = top();
      if (--cnt[color[u]] == 0) {
         --curAns;
      }
      stSz--;
   }
} ms;

void solve(int u, int p) {
   vector<pair<int, int>> nxt;
   for (int v : g[u]) {
      if (v != p) {
         nxt.emplace_back(down[v] + 1, v);
      }
   }
   if (!nxt.empty()) {
      swap(nxt[0], nxt[max_element(nxt.begin(), nxt.end()) - nxt.begin()]);
      int len = 0;
      if (nxt.size() > 1) {
         len = max_element(nxt.begin() + 1, nxt.end())->first;
      }
      for (auto p : nxt) {
         int v = p.second;
         while (!ms.empty() && dep[ms.top()] >= dep[u] - len) {
            ms.pop();
         }
         ms.push(u);
         solve(v, u);
         if (!ms.empty() && ms.top() == u) {
            ms.pop();
         }
         len = max(len, p.first);
      }
      while (!ms.empty() && dep[ms.top()] >= dep[u] - len) {
         ms.pop();
      }
   }
   ans[u] = max(ans[u], ms.curAns);
}

int main() {
   int n, m;
   scanf("%d %d", &n, &m);
   for (int i = 0; i < n - 1; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i = 1; i <= n; ++i) {
      scanf("%d", color + i);
   }
   int root = 1;
   dfs(1, 1);
   for (int rot = 0; rot < 2; ++rot) {;
      root = max_element(dep + 1, dep + 1 + n) - dep;
      dep[root] = 0;
      dfs(root, -1);
      dfsDown(root, -1);
      solve(root, -1);
   }
   for (int i = 1; i <= n; ++i) {
      printf("%d\n", ans[i]);
   }
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:91:9: 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:94:12: 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:99:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", color + i);
       ~~~~~^~~~~~~~~~~~~~~~~

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