oj.uz

Submission #128281

# Submission time Handle Problem Language Result Execution time Memory
128281 2019-07-10T15:55:37 Z IOrtroiii Unique Cities (JOI19_ho_t5) C++14
0 / 100
 251 ms 28128 KB 
#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) {
   int ans = u;
   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--;
   }
} st;

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);
      }
   }
   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 (!st.empty() && dep[st.top()] >= dep[u] - len) {
         st.pop();
      }
      st.push(u);
      solve(v, u);
      if (!st.empty() && st.top() == u) {
         st.pop();
      }
      len = max(len, p.first);
   }
   while (!st.empty() && dep[st.top()] >= dep[u] - len) {
      st.pop();
   }
   ans[u] = max(ans[u], st.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

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:13:8: warning: unused variable 'ans' [-Wunused-variable]
    int ans = u;
        ^~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:90: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:93: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:98:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", color + i);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 21880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 28128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -