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 |
|
|
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 |