oj.uz

Submission #235695

# Submission time Handle Problem Language Result Execution time Memory
235695 2020-05-29T12:05:43 Z doowey Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 10872 KB 
#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 ans = 1;
  for(int i = n - 1; i > 1; i -- ){
    for(int j = 1; j <= n; j ++ ) is[j]=false;
    if(decomp(1, i)){
      ans=i;
      break;
    }
  } 
  cout << ans << "\n";
  return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 10872 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 5060 ms 8824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -