oj.uz

Submission #235716

# Submission time Handle Problem Language Result Execution time Memory
235716 2020-05-29T13:09:09 Z doowey Lampice (COCI19_lampice) C++14
110 / 110
 4176 ms 14328 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1792 KB Output is correct
2 Correct 11 ms 1792 KB Output is correct
3 Correct 27 ms 2048 KB Output is correct
4 Correct 27 ms 1920 KB Output is correct
5 Correct 5 ms 1792 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct
7 Correct 5 ms 1792 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2212 ms 12324 KB Output is correct
2 Correct 824 ms 11684 KB Output is correct
3 Correct 748 ms 11920 KB Output is correct
4 Correct 840 ms 12408 KB Output is correct
5 Correct 1256 ms 14328 KB Output is correct
6 Correct 265 ms 9720 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3443 ms 9976 KB Output is correct
2 Correct 2554 ms 10072 KB Output is correct
3 Correct 2387 ms 10484 KB Output is correct
4 Correct 1384 ms 8056 KB Output is correct
5 Correct 1548 ms 9208 KB Output is correct
6 Correct 1854 ms 8824 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1792 KB Output is correct
2 Correct 11 ms 1792 KB Output is correct
3 Correct 27 ms 2048 KB Output is correct
4 Correct 27 ms 1920 KB Output is correct
5 Correct 5 ms 1792 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct
7 Correct 5 ms 1792 KB Output is correct
8 Correct 2212 ms 12324 KB Output is correct
9 Correct 824 ms 11684 KB Output is correct
10 Correct 748 ms 11920 KB Output is correct
11 Correct 840 ms 12408 KB Output is correct
12 Correct 1256 ms 14328 KB Output is correct
13 Correct 265 ms 9720 KB Output is correct
14 Correct 3443 ms 9976 KB Output is correct
15 Correct 2554 ms 10072 KB Output is correct
16 Correct 2387 ms 10484 KB Output is correct
17 Correct 1384 ms 8056 KB Output is correct
18 Correct 1548 ms 9208 KB Output is correct
19 Correct 1854 ms 8824 KB Output is correct
20 Correct 1559 ms 6856 KB Output is correct
21 Correct 1961 ms 8696 KB Output is correct
22 Correct 2550 ms 10208 KB Output is correct
23 Correct 682 ms 5168 KB Output is correct
24 Correct 1125 ms 7620 KB Output is correct
25 Correct 1306 ms 7032 KB Output is correct
26 Correct 2105 ms 10360 KB Output is correct
27 Correct 4176 ms 10636 KB Output is correct
28 Correct 1055 ms 5280 KB Output is correct
29 Correct 1077 ms 5340 KB Output is correct
30 Correct 1057 ms 7560 KB Output is correct
31 Correct 1412 ms 6336 KB Output is correct
32 Correct 1109 ms 9260 KB Output is correct
33 Correct 1365 ms 7800 KB Output is correct