oj.uz

Submission #253816

# Submission time Handle Problem Language Result Execution time Memory
253816 2020-07-28T18:27:39 Z Bruteforceman Lampice (COCI19_lampice) C++11
42 / 110
 5000 ms 13784 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 131;
vector <int> g[maxn];
long long power[maxn], up[maxn], down[maxn];
int sub[maxn], dep[maxn];
bool vis[maxn];
char s[maxn];
 
 
void subtree(int x, int par) {
  sub[x] = 1;
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par) {
      subtree(i, x);
      sub[x] += sub[i];
    }
  }
}
int centroid(int x, int par, int range) {
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par && sub[i] > range) {
      return centroid(i, x, range);
    }
  }
  return x;
}
void dfs(int x, int par) {
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par) {
      dep[i] = 1 + dep[x];
      down[i] = (down[x] * base + s[i]) % mod;
      up[i] = (power[dep[i]] * s[i] + up[x]) % mod;
      dfs(i, x);
    }
  }
}
void getNode(int x, int par, vector <int> &node) {
  node.push_back(x);
  for(auto i : g[x]) {
    if(!vis[i] && i != par) {
      getNode(i, x, node);
    }
  }
}
unordered_set <int> table[maxn];
bool solve(int x, int k) {
  subtree(x, 0);
  x = centroid(x, 0, sub[x] / 2);
  dep[x] = 0;
  up[x] = down[x] = s[x];
  dfs(x, 0);
  bool ans = false;
  for(int i : g[x]) {
    if(vis[i]) continue;
    vector <int> node;
    vector <pair <int, int>> cont;
    getNode(i, x, node);
    for(auto j : node) {
      if(dep[j] + 1 == k) {
        ans |= (down[j] == up[j]);    
      } else if (dep[j] < k) {
        long long value = (up[j] * power[k - dep[j] - 1] - down[j] + power[dep[j]] * s[x] + mod) % mod;
        ans |= table[k - dep[j] - 1].find(value) != table[k - dep[j] - 1].end();
        cont.emplace_back(dep[j], value);
      }
    }
    for(auto j : cont) table[j.first].insert(j.second);
  }
  vector <int> node;
  getNode(x, 0, node);
  for(auto i : node) {
    table[dep[i]].clear();
  }
  vis[x] = true;
  for(int i : g[x]) {
    if(vis[i]) continue;
    ans |= solve(i, k);
  }
  return ans;
}
 
int main() {
  int n;
  scanf("%d", &n);
  scanf("%s", s + 1);
  power[0] = 1;
  for(int i = 1; i <= n; i++) {
    power[i] = (power[i - 1] * base) % mod;
  }
  for(int i = 1; i < n; i++) {
    int p, q;
    scanf("%d %d", &p, &q);
    g[p].push_back(q);
    g[q].push_back(p);
  }
  
 
 
 
  int ans;
  int l = 1, r = (n + 1) / 2;
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    memset(vis, false, sizeof vis);
    if(solve(1, 2 * mid - 1)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  ans = 2 * l - 1;
  l = 0; r = (n / 2);
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    memset(vis, false, sizeof vis);
    if(solve(1, mid * 2)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  ans = max(ans, l * 2);
  printf("%d\n", ans);
  return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
lampice.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
lampice.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4352 KB Output is correct
2 Correct 20 ms 4480 KB Output is correct
3 Correct 51 ms 4524 KB Output is correct
4 Correct 78 ms 4480 KB Output is correct
5 Correct 3 ms 4224 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2641 ms 12424 KB Output is correct
2 Correct 3175 ms 12540 KB Output is correct
3 Correct 3549 ms 12824 KB Output is correct
4 Correct 3615 ms 13412 KB Output is correct
5 Correct 3842 ms 13784 KB Output is correct
6 Correct 3061 ms 13364 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 11020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4352 KB Output is correct
2 Correct 20 ms 4480 KB Output is correct
3 Correct 51 ms 4524 KB Output is correct
4 Correct 78 ms 4480 KB Output is correct
5 Correct 3 ms 4224 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct
8 Correct 2641 ms 12424 KB Output is correct
9 Correct 3175 ms 12540 KB Output is correct
10 Correct 3549 ms 12824 KB Output is correct
11 Correct 3615 ms 13412 KB Output is correct
12 Correct 3842 ms 13784 KB Output is correct
13 Correct 3061 ms 13364 KB Output is correct
14 Execution timed out 5063 ms 11020 KB Time limit exceeded
15 Halted 0 ms 0 KB -