Submission #235716

#	Time	Username	Problem	Language	Result	Execution time	Memory
235716		doowey	Lampice (COCI19_lampice)	C++14	110 / 110	4176 ms	14328 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 50010;
const int P = 69;
const int MOD = (int)1e9 + 9;

void add(int &a, int b){
  a += b;
  if(a >= MOD)
    a -= MOD;
  else if(a < 0)
    a += MOD;
}

int mult(int a, int b){
  return (a * 1ll * b) % MOD;
}

int pwr[N];

vector<int> T[N];
bool is[N];
int subt[N];
int dd[N];

int dep[N];
int A[N];
int B[N];

void dfs(int u, int par){
  dep[u]=A[u]=B[u]=0;
  subt[u]=1;
  for(auto x : T[u]){
    if(is[x] || x == par) continue;
    dfs(x,u);
    
    subt[u]+=subt[x];
  }
}

vector<int> lis;

void dfs1(int node, int pp){
  lis.push_back(node);
  dep[node]=dep[pp] + 1;
  A[node]=mult(A[pp], P);
  add(A[node],dd[node]);
  B[node] = B[pp];
  add(B[node], mult(pwr[dep[node]],dd[node]));
  for(auto x : T[node]){
    if(x == pp || is[x]) continue;
    dfs1(x, node);
  }
}

bool decomp(int node,int q){
  if(q<=1) return true;
  dfs(node,-1);
  int pr = -1;
  bool good = true;
  int ini = subt[node];
  if(q > ini) return false;
  while(good){
    good=false;
    for(auto x : T[node]){
      if(is[x] || x == pr) continue;
      if(subt[x] > ini/2){
        pr=node;
        node = x;
        good= true;
        break;
      }
    }
  }
  is[node]=true;
  int C = dd[node];
  set<pii> chk;
  int f1, f2;
  A[node]=0;
  dep[node]=0;
  B[node]=0;
  for(auto x : T[node]){
    if(is[x]) continue;
    lis.clear();
    dfs1(x, node);
    for(auto p : lis){
      if(dep[p] > q) continue;
      if(dep[p] + 1 == q){
        f1 = A[p];
        add(f1, mult(pwr[dep[p]], C));
        f2 = B[p];
        add(f2, C);
        if(f1 == f2) return true;
      }
      else if(dep[p] + 1 < q){
        f1 = A[p];
        add(f1, mult(C, pwr[dep[p]]));
        add(f1, -mult(B[p], pwr[q - dep[p] - 1]));
        add(f1, -mult(C, pwr[q - dep[p] - 1]));
        if(chk.count(mp(f1, q - dep[p] - 1))) return true;
      }
    }
    for(auto p : lis){
      f1 = A[p];
      add(f1,-mult(B[p],pwr[q - dep[p] - 1]));
      chk.insert(mp(f1, dep[p]));
    }
  }
  for(auto x : T[node]){
    if(!is[x]){
      if(decomp(x, q)) return true;
    }
  }
  return false;
}

int main(){
  fastIO;
  pwr[0]=1;
  for(int i = 1; i < N ; i ++ )
    pwr[i]=mult(pwr[i-1],P);
  int n;
  cin >> n;
  char q;
  for(int i = 1; i <= n; i ++ ){
    cin >> q;
    dd[i]=q-'a'+1;
  }
  int u, v;
  for(int i = 1; i < n; i ++ ){
    cin >> u >> v;
    T[u].push_back(v);
    T[v].push_back(u);
  }
  int ans = 1;
  int li = 0, ri = n + 1;
  int mid;
  while(li + 1 < ri){
    for(int i = 1; i <= n; i ++ ) is[i]=false;
    mid = (li + ri) / 2;
    if(decomp(1, mid * 2))
      li = mid;
    else
      ri = mid;
  }
  ans = max(ans, li * 2);
  li = 0, ri = n + 1;
  while(li + 1 < ri){
    for(int i = 1; i <= n; i ++ ) is[i]=false;
    mid = (li + ri) / 2;
    if(decomp(1, mid * 2 + 1))
      li = mid;
    else
      ri = mid;
  }
  ans = max(ans, li * 2 + 1);
  cout << ans << "\n";
  return 0;
}

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