Submission #1106964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106964		Persia	Lampice (COCI19_lampice)	C++14	17 / 110	5078 ms	281796 KiB

lampice

/*
    Author: Persia
    Touhou
*/
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define bit(i, x) (x >> i & 1)
#define SZ(x) (int)(x).size()
#define MASK(x) (1 << x)

using namespace std;
const int N = 5e4 + 3;
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
  return uniform_int_distribution<long long>(l, r)(rng);
}
int n, a[N];
vector<int> G[N];
int sz[N], dd[N];
int pw[2 * N];
int k;
int mx;
map<int, int> mp[N];
int PW(int x, int y) {
  int val = 1;
  while(y) {
    if(y & 1) val = (1LL * val * x) % mod;
    x = (1LL * x * x) % mod;
    y >>= 1;
  }
  return val;
}
void PreDFS(int u, int par) {
  sz[u] = 1;
  for(auto v : G[u]) if(v != par && !dd[v]) {
    PreDFS(v, u);
    sz[u] += sz[v];
  }
}
int FindCentroid(int u, int par, int nn) {
  for(auto v : G[u]) if(v != par && !dd[v]) {
    if(sz[v] > nn / 2) return FindCentroid(v, u, nn);
  }
  return u;
}
bool DFS(int u, int par, int h, int g, int d, bool flag) {
  if(d > k) return 0;
  mx = max(mx, d);
  h = (1LL * h * 31 + a[u]) % mod;
  g = (g + 1LL * a[u] * pw[d + n]) % mod;
  int val = (((h - 1LL * g * pw[k - d + n])) % mod + mod) % mod;
  if(flag == 0)  {
    if(mp[k - d][val]) return 1;
  }
  else {
    mp[d][val] = 1;
  }
  for(auto v : G[u]) if(v != par && !dd[v]) {
    if(DFS(v, u, h, g, d + 1, flag)) return 1;
  }
  return 0;
}
vector<int> del;
bool Centroid(int u) {
  PreDFS(u, -1);
  u = FindCentroid(u, -1, sz[u]);
  dd[u] = 1;
  del.push_back(u);
//  cout << u << " ";
  long long h = 0;
  long long g = a[u];
  int val = (((h - 1LL * g * pw[k - 0 + n])) % mod + mod) % mod;
  mp[0][val] = 1;
  for(auto v : G[u]) if(!dd[v]) {
    if(DFS(v, u, h, g, 1, 0)) return 1;
    DFS(v, u, h, g, 1, 1);
  }
  rep(i, 0, mx) mp[i].clear();
  mx = 0;
//  cout << u << " ";
  for(auto v : G[u]) if(!dd[v]) {
    if(Centroid(v)) return 1;
  }
  return 0;
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if(fopen("testing.txt", "r")) {
    freopen("testing.txt", "r", stdin);
    freopen("outputing.txt", "w", stdout);
  }

  cin >> n;
  pw[0 + n] = 1;
  // 0 -> n
  // n -> n + n
  // -n -> -1
  //0 - n - 1
  rep(i, 1, n) pw[i + n] = PW(31, i);
  rep(i, 0, n - 1) pw[i] = PW(pw[i + n], mod - 2);
//  rep(i, 0, n - 1) cout << (1LL * pw[i + n] * pw[i]) % mod << " ";
  rep(i, 1, n) {
    char x; cin >> x;
    a[i] = x - 'a' + 1;
  }
  rep(i, 1, n - 1) {
    int x, y; cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }

//  k = 1;
//  cout << Centroid(1);


  int l = 1, r = n / 2, res = 1;
  while(l <= r) {
    int mid = (l + r) / 2;
    k = 2 * mid - 1;
//    cout << k + 1 << " ";
    if(Centroid(1)) l = mid + 1, res = 2 * mid;
    else r = mid - 1;
    rep(i, 0, mx) {
      mp[i].clear();
    }
    for(auto i : del) dd[i] = 0;
    del.clear();
    mx = 0;
  }
  l = 0, r = (n - 1) / 2;
  while(l <= r) {
    int mid = (l + r) / 2;
    k = 2 * mid + 1 - 1;

    if(Centroid(1)) l = mid + 1, res = max(res, 2 * mid + 1);
    else r = mid - 1;
    for(auto i : del) dd[i] = 0;
    rep(i, 0, mx) {
      mp[i].clear();
    }
    del.clear();
    mx = 0;
  }
  cout << res;
}

Compilation message (stderr)

lampice.cpp: In function 'int main(int, char**)':
lampice.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen("testing.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     freopen("outputing.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37