Xmas Contest 2015 夜の部

Submission #1436057

Source codeソースコード

#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

Task問題 D - Destroy the Duplicated Poem
User nameユーザ名 ຣസںƙᘓ
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 924 Byte
File nameファイル名
Exec time実行時間 368 ms
Memory usageメモリ使用量 71284 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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