結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
![]() |
提出日時 | 2024-05-22 16:18:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 985 ms / 4,000 ms |
コード長 | 1,742 bytes |
コンパイル時間 | 396 ms |
コンパイル使用メモリ | 58,760 KB |
最終ジャッジ日時 | 2025-02-21 16:26:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:75:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 75 | scanf("%d%d%d", &n, &l, &qn); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~ main.cpp:78:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | scanf("%s", s); | ~~~~~^~~~~~~~~ main.cpp:87:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 87 | scanf("%d", &op); | ~~~~~^~~~~~~~~~~ main.cpp:92:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 92 | scanf("%d%s%s", &k, sc, sd); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:100:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 100 | scanf("%s", s); | ~~~~~^~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2761.cc: No.2761 Substitute and Search - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 1000; const int MAX_L = 3000; /* typedef */ using vi = vector<int>; struct Node { int cs[26], s; Node(): s(0) {} }; /* global variables */ Node buf[MAX_N * MAX_L]; int bpt = 0; char s[MAX_L + 4]; int ts[MAX_L][26]; /* subroutines */ int alloc_node() { int u = bpt++; fill(buf[u].cs, buf[u].cs + 26, -1); buf[u].s = 0; return u; } void trie_add(int l, char s[]) { int u = 0; for (int i = 0; i < l; i++) { int ci = s[i] - 'a'; if (buf[u].cs[ci] < 0) buf[u].cs[ci] = alloc_node(); u = buf[u].cs[ci]; buf[u].s++; } } int trie_count(char s[]) { vi us(1, 0); for (int i = 0; s[i] >= ' '; i++) { int ci = s[i] - 'a'; vi vs; for (auto u: us) for (int j = 0; j < 26; j++) if (ts[i][j] == ci && buf[u].cs[j] >= 0) vs.push_back(buf[u].cs[j]); swap(us, vs); } int sum = 0; for (auto u: us) sum += buf[u].s; return sum; } /* main */ int main() { alloc_node(); int n, l, qn; scanf("%d%d%d", &n, &l, &qn); for (int i = 0; i < n; i++) { scanf("%s", s); trie_add(l, s); } for (int i = 0; i < l; i++) for (int j = 0; j < 26; j++) ts[i][j] = j; while (qn--) { int op; scanf("%d", &op); if (op == 1) { int k; char sc[4], sd[4]; scanf("%d%s%s", &k, sc, sd); k--; int c = sc[0] - 'a', d = sd[0] - 'a'; for (int j = 0; j < 26; j++) if (ts[k][j] == c) ts[k][j] = d; } else { scanf("%s", s); int cnt = trie_count(s); printf("%d\n", cnt); } } return 0; }