oj.uz

Submission #253823

# Submission time Handle Problem Language Result Execution time Memory
253823 2020-07-28T18:51:33 Z Bruteforceman Lampice (COCI19_lampice) C++11
42 / 110
 5000 ms 12184 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;
}
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;
  unordered_set <pair <int, int>, HASH> 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:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
lampice.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
lampice.cpp:101: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 16 ms 1664 KB Output is correct
3 Correct 52 ms 1792 KB Output is correct
4 Correct 74 ms 1820 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 2735 ms 10836 KB Output is correct
2 Correct 3729 ms 11616 KB Output is correct
3 Correct 4142 ms 11840 KB Output is correct
4 Correct 4230 ms 12160 KB Output is correct
5 Correct 4456 ms 12184 KB Output is correct
6 Correct 3442 ms 10136 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4865 ms 8796 KB Output is correct
2 Execution timed out 5076 ms 8240 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 1536 KB Output is correct
2 Correct 16 ms 1664 KB Output is correct
3 Correct 52 ms 1792 KB Output is correct
4 Correct 74 ms 1820 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 2735 ms 10836 KB Output is correct
9 Correct 3729 ms 11616 KB Output is correct
10 Correct 4142 ms 11840 KB Output is correct
11 Correct 4230 ms 12160 KB Output is correct
12 Correct 4456 ms 12184 KB Output is correct
13 Correct 3442 ms 10136 KB Output is correct
14 Correct 4865 ms 8796 KB Output is correct
15 Execution timed out 5076 ms 8240 KB Time limit exceeded
16 Halted 0 ms 0 KB -