fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mnum = 1e5 + 5;
  5. const int maxn = 3e5 + 5;
  6. //
  7. int n, m, p[maxn];
  8. string s[maxn];
  9. //
  10. namespace Trie
  11. {
  12.     struct Node
  13.     {
  14.         int cnt;
  15.         long long val;
  16.         Node *par, *child[26];
  17.         //
  18.         Node (void) : cnt(0), val(0)
  19.         {
  20.             fill(child, child + 26, nullptr);
  21.         }
  22.     };
  23.     //
  24.     Node *root = new Node();
  25.     Node *en[maxn];
  26.     //
  27.     void insert (int id)
  28.     {
  29.         int c;
  30.         Node *p = root;
  31.         //
  32.         for (char f : s[id])
  33.         {
  34.             c = f - 'A';
  35.             if (p->child[c] == nullptr)
  36.                 p->child[c] = new Node(),
  37.                 p->child[c]->par = p;
  38.             p = p->child[c];
  39.             ++p->cnt;
  40.         }
  41.         en[id] = p;
  42.     }
  43.     void erase (int id, long long v)
  44.     {
  45.         Node *temp, *p = en[id];
  46.         //
  47.         while (p != root)
  48.         {
  49.             temp = p->par;
  50.             if (--p->cnt == 0)
  51.                 delete(p);
  52.             p = temp;
  53.             p->val = max(p->val, v);
  54.         }
  55.     }
  56. }
  57. //
  58. int check_sub (void)
  59. {
  60.     int mx = 0;
  61.     //
  62.     for (int i = 1; i <= n; ++i)
  63.         mx = max(mx, (int)s[i].length());
  64.     if (n <= 100 && mx <= 100 && m <= 100)
  65.         return 1;
  66.     if (m == 0)
  67.         return 2;
  68.     return 3;
  69. }
  70. namespace subtask_1
  71. {
  72.     vector<int> lucky[mnum];
  73.     long long dp[maxn];
  74.     //
  75.     void solve (void)
  76.     {
  77.         for (int u, v; m--;)
  78.             cin >> u >> v,
  79.             lucky[u].emplace_back(v),
  80.             lucky[v].emplace_back(u);
  81.  
  82.         for (int i = 1; i <= n; ++i)
  83.         {
  84.             for (int j = 1; j < i; ++j)
  85.                 if (s[j].size() > s[i].size() && s[j].substr(0, s[i].size()) == s[i])
  86.                     dp[i] = max(dp[i], dp[j]);
  87.             for (int x : lucky[p[i]])
  88.                 for (int j = 1; j < i; ++j)
  89.                     if (p[j] == x)
  90.                         dp[i] = max(dp[i], dp[j]);
  91.             dp[i] += p[i];
  92.         }
  93.  
  94.         cout << *max_element(dp + 1, dp + n + 1);
  95.     }
  96. }
  97. namespace subtask_2
  98. {
  99.     void solve (void)
  100.     {
  101.         long long temp, ans = 0;
  102.         //
  103.         for (int i = 1; i <= n; ++i)
  104.             Trie::insert(i);
  105.         for (int i = 1; i <= n; ++i)
  106.             temp = Trie::en[i]->val + p[i],
  107.             ans = max(ans, temp),
  108.             Trie::erase(i, temp);
  109.         cout << ans;
  110.     }
  111. }
  112. namespace subtask_3
  113. {
  114.     const int orz = 500;
  115.     //
  116.     vector<int> lucky[mnum];
  117.     vector<int> heavy[mnum];
  118.     long long num[mnum], lazy[mnum];
  119.     //
  120.     void build (void)
  121.     {
  122.         for (int u = 1; u < mnum; ++u)
  123.             for (int v : lucky[u])
  124.                 if (lucky[v].size() > orz)
  125.                     heavy[u].emplace_back(v);
  126.     }
  127.     void update (int u, long long val)
  128.     {
  129.         lazy[u] = val;
  130.         if (lucky[u].size() <= orz)
  131.             for (int v : lucky[u])
  132.                 num[v] = max(num[v], lazy[u]);
  133.     }
  134.     long long get (int u)
  135.     {
  136.         long long res = num[u];
  137.         //
  138.         for (int v : heavy[u])
  139.             res = max(res, lazy[v]);
  140.         return res;
  141.     }
  142.     //
  143.     void solve (void)
  144.     {
  145.         long long temp, ans = 0;
  146.         //
  147.         for (int u, v; m--;)
  148.             cin >> u >> v,
  149.             lucky[u].emplace_back(v),
  150.             lucky[v].emplace_back(u);
  151.  
  152.         build();
  153.         for (int i = 1; i <= n; ++i)
  154.             Trie::insert(i);
  155.         for (int i = 1; i <= n; ++i)
  156.         {
  157.             temp = max(Trie::en[i]->val, get(p[i])) + p[i];
  158.             ans = max(ans, temp);
  159.             Trie::erase(i, temp);
  160.             update(p[i], temp);
  161.         }
  162.  
  163.         cout << ans;
  164.     }
  165. }
  166. //
  167. void process (void)
  168. {
  169.     cin >> n >> m;
  170.     for (int i = 1; i <= n; ++i)
  171.         cin >> s[i] >> p[i];
  172.     //
  173.     int sub = check_sub();
  174.     //
  175.     if (sub == 1)
  176.         return subtask_1::solve();
  177.     if (sub == 2)
  178.         return subtask_2::solve();
  179.     subtask_3::solve();
  180. }
  181. //
  182. signed main (void)
  183. {
  184.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  185.     process();
  186. }
  187.  
Success #stdin #stdout 0.01s 24148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kpAJNf
https://o...content-available-to-author-only...i.info/problem/voi21_bonus
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!