SHARE
TWEET

Untitled

MegaVerkruzo Nov 12th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5. #include <deque>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <cstdio>
  9.  
  10. using namespace std;
  11.  
  12. const int INF = 2e9;
  13.  
  14. long long sum = 0;
  15.  
  16. vector<int> used;
  17.  
  18. vector<pair<pair<int, int>, int>> answer;
  19.  
  20. bool cmp (pair<string, int>& left, pair<string, int>& right) {
  21.     return left.first.length() > right.first.length();
  22. }
  23.  
  24. void dfs(vector<vector<pair<int, int>>>& pr, vector<vector<int>>& dp, vector<vector<pair<int, char>>>& g, vector<pair<int, char>>& obr, vector<vector<int>>& tok, int now) {
  25.     for (auto next : g[now]) {
  26.         if (dp[now][next.first] == INF) {
  27.             sum = 1e18;
  28.             return;
  29.         } else {
  30.             if (used[next.first] == 1) {
  31.                 int r = pr[now][next.first].second;
  32.                 int l = pr[now][next.first].first;
  33.                 sum += dp[now][next.first];
  34.                 answer.push_back({{l, r}, tok[now][next.first]});
  35.                 while (r >= now) {
  36.                     used[r] = 0;
  37.                     r = obr[r].first;
  38.                 }
  39.             }
  40.             dfs(pr, dp, g, obr, tok, next.first);
  41.         }
  42.     }
  43. }
  44.  
  45. void uf(vector<pair<string, int>>& s, vector<vector<int>>& sd, vector<int>& now, vector<vector<pair<int, char>>>& g, string& yea, int e) {
  46.     now.push_back(e);
  47.     if (g[e].size() == 0) {
  48.         s.push_back({yea, s.size()});
  49.         sd.push_back(now);
  50.     }
  51.     for (auto next : g[e]) {
  52.         yea.push_back(next.second);
  53.         uf(s, sd, now, g, yea, next.first);
  54.         yea.pop_back();
  55.     }
  56.     now.pop_back();
  57. }
  58.  
  59. int main()
  60. {
  61.     freopen("input.txt", "r", stdin);
  62.     int n, m, t;
  63.     cin >> n >> m >> t;
  64.     vector<vector<pair<int, char>>> g(n + 1);
  65.     vector<pair<int, char>> obr(n + 1);
  66.     for (int i = 2; i <= n; ++i) {
  67.         int x;
  68.         char c;
  69.         cin >> x >> c;
  70.         g[x].push_back({i, c});
  71.         obr[i].first = x;
  72.         obr[i].second = c;
  73.     }
  74.     unordered_map<string, pair<int, int>> about;
  75.     vector<string> buf;
  76.     for (int i = 1; i <= m; ++i) {
  77.         int x;
  78.         cin >> x;
  79.         string s;
  80.         cin >> s;
  81.         if (about[s].first != 0 && x < about[s].first || about[s].first == 0) {
  82.             about[s].first = x;
  83.             about[s].second = i;
  84.         }
  85.         buf.push_back(s);
  86.     }
  87.     sort(buf.begin(), buf.end());
  88.     vector<string> main;
  89.     main.push_back(*buf.begin());
  90.     for (int i = 1; i < m; ++i) {
  91.         if (main.back() != buf[i]) {
  92.             main.push_back(buf[i]);
  93.         }
  94.     }
  95.     vector<vector<int>> dp(n + 1, vector<int> (n + 1, INF));
  96.     vector<vector<pair<int, int>>> pr(n + 1, vector<pair<int, int>> (n + 1));
  97.     vector<vector<int>> tok(n + 1, vector<int> (n + 1));
  98.     vector<vector<int>> len(n + 1, vector<int> (n + 1));
  99.     vector<vector<int>> sd;
  100.     vector<pair<string, int>> s;
  101.     vector<int> now;
  102.     string yea;
  103.     uf(s, sd, now, g, yea, 1);
  104.     sort(s.begin(), s.end(), cmp);
  105.     for (int i = 0; i < s.size(); ++i) {
  106.         for (int l = s[i].first.length(); l >= 1; ++l) {
  107.             for (int j = 0; j < s[i].first.length() - l; ++j) {
  108.                 string buf_ = s[i].first.substr(j, l);
  109.                 auto it_1 = lower_bound(main.begin(), main.end(), buf_), it_2 = upper_bound(main.begin(), main.end(), buf_);
  110.                 if (it_1 != main.end() && ++it_1 != it_2) {
  111.                     for (int start = j + l; start > j; --j) {
  112.                         if (dp[sd[s[i].second][start - 1]][sd[s[i].second][start]] > about[buf_].first ||
  113.                             dp[sd[s[i].second][start - 1]][sd[s[i].second][start]] == about[buf_].first &&
  114.                             len[sd[s[i].second][start - 1]][sd[s[i].second][start]] < buf_.length()) {
  115.  
  116.                             dp[sd[s[i].second][start - 1]][sd[s[i].second][start]] = about[buf_].first;
  117.                             pr[sd[s[i].second][start - 1]][sd[s[i].second][start]].first = sd[s[i].second][j];
  118.                             pr[sd[s[i].second][start - 1]][sd[s[i].second][start]].second = sd[s[i].second][j + l];
  119.                             len[sd[s[i].second][start - 1]][sd[s[i].second][start]] = buf_.length();
  120.                             tok[sd[s[i].second][start - 1]][sd[s[i].second][start]] = about[buf_].second;
  121.                         }
  122.                     }
  123.                 }
  124.             }
  125.         }
  126.     }
  127.     used.resize(n + 1, 1);
  128.     dfs(pr, dp, g, obr, tok, 1);
  129.     if (sum > 1e17) {
  130.         cout << -1;
  131.     } else {
  132.         cout << sum;
  133.         if (t == 1) {
  134.             cout << "\n" << answer.size() << "\n";
  135.             for (int i  = 0; i < answer.size(); ++i) {
  136.                 cout << answer[i].first.first << " " << answer[i].first.second << " " << answer[i].second << "\n";
  137.             }
  138.         }
  139.     }
  140.  
  141.     return 0;
  142. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top