oj.uz

Submission #253825

# Submission time Handle Problem Language Result Execution time Memory
253825 2020-07-28T18:54:46 Z Bruteforceman Lampice (COCI19_lampice) C++11
17 / 110
 5000 ms 10760 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 50021;
vector <int> g[maxn];
long long power[maxn], up[maxn], down[maxn];
int sub[maxn], dep[maxn];
bool vis[maxn];
char s[maxn];

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

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);
    }
  }
}
int getHash(int dep, long long h) {
  return (h * base + dep) % mod;
}

unordered_set <pair <int, int>, HASH> table;
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;
  table.clear();
  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);
  }
  table.max_load_factor(0.25); //updated !
  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:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
lampice.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
lampice.cpp:103: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 1536 KB Output is correct
2 Correct 22 ms 1728 KB Output is correct
3 Correct 79 ms 1792 KB Output is correct
4 Correct 95 ms 1912 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1536 KB Output is correct
2 Correct 22 ms 1728 KB Output is correct
3 Correct 79 ms 1792 KB Output is correct
4 Correct 95 ms 1912 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Execution timed out 5086 ms 10760 KB Time limit exceeded
9 Halted 0 ms 0 KB -