oj.uz

Submission #984989

# Submission time Handle Problem Language Result Execution time Memory
984989 2024-05-17T09:04:38 Z vjudge1 Lampice (COCI19_lampice) C++17
110 / 110
 1031 ms 20032 KB 
#include <bits/stdc++.h>
using namespace std;

struct Tree {
  vector<int> nodes;  // original mapping
  vector<vector<int>> adj;

  void init(int num_nodes) {
    nodes.resize(num_nodes);
    adj.resize(num_nodes);
  }

  void clear() {
    nodes.clear();
    adj.clear();
  }
};

class Decompositor {
 public:
  Decompositor(const Tree &tree) : tree_(tree), next_label_(0) {
    size_.resize(tree.nodes.size());
    done_.resize(tree.nodes.size());
    queue_.push(0);
  }

  // vraca sljedece dekomponirano stablo
  bool NextTree(Tree &decomposed_tree) {
    decomposed_tree.clear();
    int node = GetQueuedNode();
    if (node == -1) return false;
    
    CalculateSize(node);
    int centroid = FindCentroid(node, size_[node]);
    assert(centroid != -1);
    
    // build tree
    decomposed_tree.init(size_[node]);
    next_label_ = 0;
    BuildTree(decomposed_tree, centroid);
    
    // mark labels
    done_[centroid] = true;
    for (int y : tree_.adj[centroid])
      queue_.push(y);
    return true;
  }

 private:
  const Tree &tree_;
  queue<int> queue_;
  vector<int> size_;
  vector<bool> done_;
  int next_label_;

  int GetQueuedNode() {
    for (; !queue_.empty(); queue_.pop()) {
      int x = queue_.front();
      if (!done_[x]) return x;
    }
    return -1;
  }

  void CalculateSize(int x, int prev = -1) {
    size_[x] = 1;
    for (int y : tree_.adj[x]) {
      if (y == prev || done_[y]) continue;
      CalculateSize(y, x);
      size_[x] += size_[y];
    }
  }

  int FindCentroid(int x, int tot_size, int prev = -1) {
    if (IsCentroid(x, tot_size)) return x;
    for (int y : tree_.adj[x]) {
      if (y == prev || done_[y]) continue;
      int q = FindCentroid(y, tot_size, x);
      if (q != -1) return q;
    }
    return -1;
  }

  bool IsCentroid(int x, int tot_size) {
    bool flag = false;
    if (2 * (tot_size - size_[x]) > tot_size) return false;
    for (int y : tree_.adj[x]) {
      if (done_[x] || size_[y] > size_[x]) continue;
      if (2 * size_[y] > tot_size) return false;
    }
    return true;
  }

  void BuildTree(Tree &target, int x, int prev = -1, int prev_label = -1) {
    int label = next_label_++;
    target.nodes[label] = x;
    if (prev_label != -1)
      target.adj[prev_label].push_back(label);
    for (int y : tree_.adj[x]) {
      if (y == prev || done_[y]) continue;
      BuildTree(target, y, x, label);
    }
  }
};

const int MAXN = 100100;
char input[MAXN];

class TreeSolver {
 public:
  TreeSolver(const Tree &tree): tree_(tree) {
    hash_down_.resize(tree.nodes.size());
    hash_up_.resize(tree.nodes.size());
    hash_set_.resize(tree.nodes.size());
    stack_.reserve(tree.nodes.size());
  }

  void Build(int x = 0, int dep = 0, long long hdown = 0, long long hup = 0) {
    const char c = input[tree_.nodes[x]];
    hash_down_[x] = hdown * BASE + c;
    hash_up_[x] = hup + power_[dep] * c;
    for (int y : tree_.adj[x]) {
      Build(y, dep + 1, hash_down_[x], hash_up_[x]);
    }
  }

  int Solve() {
    return max(2 * Run(0) + 1, 2 * Run(1));
  }

  int Run(int k) {
    int lo = 0, hi = (int)tree_.nodes.size();
    while (lo < hi) {
      int mid = (lo + hi + 1) / 2;
      if (Check(mid, k)) lo = mid;
      else hi = mid - 1;
    }
    return lo;
  }
  
  static void InitPowers() {
    power_[0] = 1;
    for (int i = 1; i < MAXN; ++i)
      power_[i] = power_[i - 1] * BASE;
  }

 private:
  static const int BASE = 31337;
  static long long power_[MAXN];
  Tree tree_;
  vector<long long> hash_down_;
  vector<long long> hash_up_;
  vector<unordered_set<long long>> hash_set_;
  vector<int> stack_;

  void SetHashes(int x, int dep) {
    hash_set_[dep].insert(hash_down_[x]);
    for (int y : tree_.adj[x])
      SetHashes(y, dep + 1);
  }

  void ResetHashes() {
    for (auto &it : hash_set_)
      it.clear();
  }

  // k 0 za neparno, 1 za parno
  bool Check(int len, int k) {
    // pazi na prazni string
    if (len == 0 && k == 1) return true;
    stack_.clear();
    stack_.push_back(0);
    const int n = (int)tree_.adj[0].size();
    for (int step = 0; step < 2; ++step) {
      ResetHashes();
      for (int i = 0; i < n; ++i) {
        const int node = tree_.adj[0][i];
        if (i > 0 && CheckSubtree(len, node, k)) return true;
        if (i + 1 != n) SetHashes(node, 1);
      }
      reverse(tree_.adj[0].begin(), tree_.adj[0].end());
    }
    return false;
  }

  bool CheckSubtree(int len, int x, int k) {
    const int dep = (int)stack_.size();
    stack_.push_back(x);
    bool ret = false;
    if (dep >= len) {
      if (CheckChain(len, dep, k)) {
        stack_.pop_back();
        return true;
      }
    }
    for (int y : tree_.adj[x]) {
      if (CheckSubtree(len, y, k)) {
        stack_.pop_back();
        return true;
      }
    }
    stack_.pop_back();
    return false;
  }

  bool CheckChain(int len, int dep, int k) {
    int tot_len = 2 * len - k;
    if (dep >= tot_len) {
      long long hdown = hash_down_[stack_.back()];
      long long hup = hash_up_[stack_.back()];
      int i = dep - tot_len;
      if (i > 0) {
        hdown -= power_[tot_len + 1] * hash_down_[stack_[i - 1]];
        hup -= hash_up_[stack_[i - 1]];
      }
      return hdown * power_[i] == hup;
    }
    int tail = tot_len - dep;
    int head = dep - tail;
    if (hash_down_[stack_[head]] != hash_up_[stack_[head]])
      return false;
    long long hdown = hash_down_[stack_.back()];
    if (head > 0) hdown -= power_[tail + 1] * hash_down_[stack_[head - 1]];
    return hash_set_[tail].find(hdown) != hash_set_[tail].end();
  }
};

long long TreeSolver::power_[MAXN];

void LoadTree(Tree &tree) {
  int n;
  scanf("%d", &n);
  scanf("%s", input);
  tree.init(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    tree.adj[u].push_back(v);
    tree.adj[v].push_back(u);
  }
}

int main(void) {
  TreeSolver::InitPowers();
  
  Tree tree;
  LoadTree(tree);
  Decompositor decomp(tree);

  // border case :/
  if (tree.nodes.size() == 2 && input[0] == input[1]) {
    printf("2\n");
    return 0;
  }

  int ans = 0;
  for (Tree decomp_tree; decomp.NextTree(decomp_tree);) {
    TreeSolver solver(decomp_tree);
    solver.Build();
    ans = max(ans, solver.Solve());
  }

  printf("%d\n", ans);
  
  return 0;
}

Compilation message

lampice.cpp: In member function 'bool Decompositor::IsCentroid(int, int)':
lampice.cpp:84:10: warning: unused variable 'flag' [-Wunused-variable]
   84 |     bool flag = false;
      |          ^~~~
lampice.cpp: In member function 'bool TreeSolver::CheckSubtree(int, int, int)':
lampice.cpp:188:10: warning: unused variable 'ret' [-Wunused-variable]
  188 |     bool ret = false;
      |          ^~~
lampice.cpp: In function 'void LoadTree(Tree&)':
lampice.cpp:231:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
lampice.cpp:232:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |   scanf("%s", input);
      |   ~~~~~^~~~~~~~~~~~~
lampice.cpp:236:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 5 ms 1372 KB Output is correct
3 Correct 13 ms 1628 KB Output is correct
4 Correct 14 ms 1628 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 17536 KB Output is correct
2 Correct 555 ms 17952 KB Output is correct
3 Correct 542 ms 18268 KB Output is correct
4 Correct 575 ms 19204 KB Output is correct
5 Correct 644 ms 20032 KB Output is correct
6 Correct 530 ms 19792 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 17016 KB Output is correct
2 Correct 674 ms 16464 KB Output is correct
3 Correct 700 ms 16208 KB Output is correct
4 Correct 562 ms 16720 KB Output is correct
5 Correct 599 ms 15188 KB Output is correct
6 Correct 508 ms 13660 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 5 ms 1372 KB Output is correct
3 Correct 13 ms 1628 KB Output is correct
4 Correct 14 ms 1628 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 558 ms 17536 KB Output is correct
9 Correct 555 ms 17952 KB Output is correct
10 Correct 542 ms 18268 KB Output is correct
11 Correct 575 ms 19204 KB Output is correct
12 Correct 644 ms 20032 KB Output is correct
13 Correct 530 ms 19792 KB Output is correct
14 Correct 743 ms 17016 KB Output is correct
15 Correct 674 ms 16464 KB Output is correct
16 Correct 700 ms 16208 KB Output is correct
17 Correct 562 ms 16720 KB Output is correct
18 Correct 599 ms 15188 KB Output is correct
19 Correct 508 ms 13660 KB Output is correct
20 Correct 538 ms 12552 KB Output is correct
21 Correct 703 ms 13396 KB Output is correct
22 Correct 875 ms 14180 KB Output is correct
23 Correct 230 ms 11096 KB Output is correct
24 Correct 644 ms 13916 KB Output is correct
25 Correct 612 ms 13652 KB Output is correct
26 Correct 853 ms 15952 KB Output is correct
27 Correct 1031 ms 15184 KB Output is correct
28 Correct 465 ms 13148 KB Output is correct
29 Correct 489 ms 13500 KB Output is correct
30 Correct 640 ms 15416 KB Output is correct
31 Correct 526 ms 13660 KB Output is correct
32 Correct 553 ms 16464 KB Output is correct
33 Correct 441 ms 14516 KB Output is correct