Submission #1436057


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;

struct Node {
  vector<int> to;
  int len, mp, kmp;
  Node():len(0),mp(-1),kmp(-1) {}
} t[500005];
string c;

vector<int> vs;
string s;
void dfs(int v) {
  for (int u : t[v].to) {
    vs.push_back(u); s += c[u-1];
    t[u].len = s.size();
    { // mp
      int j = t[v].mp;
      while (j != -1 && s.back() != s[j]) j = t[vs[j]].kmp;
      t[u].mp = j+1;
    }
    { // kmp
      int j = t[v].mp;
      if (j != -1 && s.back() == s[j]) t[u].kmp = t[vs[j]].kmp;
      else t[u].kmp = j;
    }
    dfs(u);
    vs.pop_back(); s.pop_back();
  }
}

int main() {
  int n;
  cin >> n;
  rep(i,n) {
    int a;
    cin >> a;
    t[a].to.push_back(i+1);
  }
  cin >> c;
  dfs(0);
  rep(i,n) {
    printf("%d\n", t[i+1].len - t[i+1].mp);
  }
  return 0;
}




















Submission Info

Submission Time
Task D - Destroy the Duplicated Poem
User snuke
Language C++14 (GCC 5.4.1)
Score 100
Code Size 924 Byte
Status AC
Exec Time 368 ms
Memory 71284 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 24
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All btree_01.txt, btree_02.txt, btree_03.txt, deep_01.txt, deep_02.txt, deep_03.txt, deep_rand_01.txt, deep_rand_02.txt, deep_rand_03.txt, deep_rand_04.txt, hand_01.txt, hand_02.txt, kmp_killer_01.txt, kmp_killer_02.txt, kmp_killer_03.txt, periodic_01.txt, periodic_02.txt, periodic_03.txt, periodic_04.txt, random_01.txt, random_02.txt, random_03.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
btree_01.txt AC 298 ms 29188 KB
btree_02.txt AC 294 ms 29700 KB
btree_03.txt AC 303 ms 29572 KB
deep_01.txt AC 334 ms 58744 KB
deep_02.txt AC 335 ms 58744 KB
deep_03.txt AC 368 ms 54524 KB
deep_rand_01.txt AC 358 ms 59384 KB
deep_rand_02.txt AC 347 ms 60024 KB
deep_rand_03.txt AC 348 ms 55548 KB
deep_rand_04.txt AC 325 ms 69368 KB
hand_01.txt AC 7 ms 19840 KB
hand_02.txt AC 7 ms 19712 KB
kmp_killer_01.txt AC 323 ms 71284 KB
kmp_killer_02.txt AC 319 ms 59516 KB
kmp_killer_03.txt AC 302 ms 48000 KB
periodic_01.txt AC 332 ms 32388 KB
periodic_02.txt AC 326 ms 32388 KB
periodic_03.txt AC 332 ms 31748 KB
periodic_04.txt AC 324 ms 33668 KB
random_01.txt AC 343 ms 29444 KB
random_02.txt AC 350 ms 29700 KB
random_03.txt AC 352 ms 29828 KB
sample_01.txt AC 7 ms 19840 KB
sample_02.txt AC 7 ms 19840 KB