oj.uz

Submission #158337

# Submission time Handle Problem Language Result Execution time Memory
158337 2019-10-16T13:53:44 Z mhy908 Split the sequence (APIO14_sequence) C++14
0 / 100
 262 ms 131076 KB 
#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

sequence.cpp: In function 'int main()':
sequence.cpp:95:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
       scanf("%d", color[i]);
                   ~~~~~~~~^
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5112 KB Integer 0 violates the range [1, 6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

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