oj.uz

Submission #253820

# Submission time Handle Problem Language Result Execution time Memory
253820 2020-07-28T18:36:04 Z Bruteforceman Lampice (COCI19_lampice) C++11
42 / 110
 5000 ms 13340 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);
    }
  }
}
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;
  set <pair <int, int>> table;
  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.find(make_pair(k - dep[j] - 1, value)) != table.end();
        cont.emplace_back(dep[j], value);
      }
    }
    for(auto j : cont) table.insert(j);
  }
  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:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
lampice.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
lampice.cpp:92: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 6 ms 1664 KB Output is correct
2 Correct 16 ms 1664 KB Output is correct
3 Correct 52 ms 1792 KB Output is correct
4 Correct 80 ms 1792 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2516 ms 11216 KB Output is correct
2 Correct 3425 ms 11424 KB Output is correct
3 Correct 3754 ms 11860 KB Output is correct
4 Correct 3963 ms 12300 KB Output is correct
5 Correct 4033 ms 13340 KB Output is correct
6 Correct 3499 ms 10860 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4486 ms 9916 KB Output is correct
2 Execution timed out 5094 ms 9460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1664 KB Output is correct
2 Correct 16 ms 1664 KB Output is correct
3 Correct 52 ms 1792 KB Output is correct
4 Correct 80 ms 1792 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 2516 ms 11216 KB Output is correct
9 Correct 3425 ms 11424 KB Output is correct
10 Correct 3754 ms 11860 KB Output is correct
11 Correct 3963 ms 12300 KB Output is correct
12 Correct 4033 ms 13340 KB Output is correct
13 Correct 3499 ms 10860 KB Output is correct
14 Correct 4486 ms 9916 KB Output is correct
15 Execution timed out 5094 ms 9460 KB Time limit exceeded
16 Halted 0 ms 0 KB -