제출 #235694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235694		doowey	Lampice (COCI19_lampice)	C++14	0 / 110	5073 ms	11384 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> 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]);
  add(B[node],pwr[dep[node]]);
  add(B[node], B[pp]);
  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];
  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> dd;
  int f1, f2;
  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(dd.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]));
      dd.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 l = 0, r = n + 1;
  int mid;
  while(l + 1 < r){
    mid = (l + r) / 2;
    for(int i = 1; i <= n; i ++ )
      is[i]=false;
    if(decomp(1, mid * 2)){
      l = mid;
    }
    else{
      r = mid;
    }
  }
  int ans = 1;
  ans = max(ans, l * 2);
  l = 0, r = n + 1;
  while(l + 1 < r){
    mid = (l + r) / 2;
    for(int i = 1; i <= n; i ++ )
      is[i]=false;
    if(decomp(1, mid * 2 + 1))
      l = mid;
    else
      r = mid;
  }
  ans = max(ans, l * 2 + 1);
  cout << ans << "\n";
  return 0;
}

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