Submission #158339

#	Time	Username	Problem	Language	Result	Execution time	Memory
158339		mhy908	Split the sequence (APIO14_sequence)	C++14	0 / 100	257 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
vector<int> g[200010];
int color[200010];
int ans[200010];
int dep[200010], down[200010];
int n, m;

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 data{
   int stSz;
   int st[200010];
   int cnt[200010];
   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() {
   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)

sequence.cpp: In function 'int main()':
sequence.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:90:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &u, &v);
       ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:95: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 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29