SHARE
TWEET

Untitled

MegaVerkruzo Nov 12th, 2019 61 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. 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) {
  21.     for (auto next : g[now]) {
  22.         if (dp[now][next.first] == INF) {
  23.             sum = 1e18;
  24.             return;
  25.         } else {
  26.             if (used[next.first] == 1) {
  27.                 int r = pr[now][next.first].second;
  28.                 int l = pr[now][next.first].first;
  29.                 sum += dp[now][next.first];
  30.                 answer.push_back({{l, r}, tok[now][next.first]});
  31.                 while (r >= now) {
  32.                     used[r] = 0;
  33.                     r = obr[r].first;
  34.                 }
  35.             }
  36.             dfs(pr, dp, g, obr, tok, next.first);
  37.         }
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     //freopen("input.txt", "r", stdin);
  44.     unordered_map <string, int> kl;
  45.     unordered_map <string, int> num;
  46.     int n, m, t;
  47.     cin >> n >> m >> t;
  48.     vector<vector<pair<int, char>>> g(n + 1);
  49.     vector<pair<int, char>> obr(n + 1);
  50.     for (int i = 2; i <= n; ++i) {
  51.         int x;
  52.         char c;
  53.         cin >> x >> c;
  54.         g[x].push_back({ i, c });
  55.         obr[i].first = x;
  56.         obr[i].second = c;
  57.     }
  58.     vector<vector<int>> heig;
  59.     heig.reserve(1000);
  60.     for (int i = 1; i <= n; ++i) {
  61.         if (g[i].size() == 0) {
  62.             int h = 0;
  63.             int now = i;
  64.             while (now != 1) {
  65.                 now = obr[now].first;
  66.                 h++;
  67.             }
  68.             while (heig.size() <= h) {
  69.                 heig.push_back({});
  70.             }
  71.             heig[h].push_back(i);
  72.         }
  73.     }
  74.     vector<string> merd(m);
  75.     vector<string> mer;
  76.     mer.reserve(100000);
  77.     for (int i = 0; i < m; ++i) {
  78.         int x;
  79.         string s;
  80.         cin >> x >> s;
  81.         merd[i] = s;
  82.         if (kl[s] != 0 && x < kl[s]) {
  83.             kl[s] = x;
  84.             num[s] = i + 1;
  85.         } else {
  86.             kl[s] = x;
  87.             num[s] = i + 1;
  88.         }
  89.     }
  90.     sort(merd.begin(), merd.end());
  91.     mer.push_back(merd[0]);
  92.     for (int i = 1; i < merd.size(); ++i) {
  93.         if (mer.back() != merd[i]) {
  94.             mer.push_back(merd[i]);
  95.         }
  96.     }
  97.     vector<vector<pair<int, int>>> pr(n + 1, vector<pair<int, int>> (n + 1));
  98.     vector<vector<int>> tok(n + 1, vector<int> (n + 1));
  99.     vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
  100.     vector<int> start;
  101.     for (int i = heig.size() - 1; i > 0; --i) {
  102.         for (int l = 0; l < heig[i].size(); ++l) {
  103.             start.push_back(heig[i][l]);
  104.         }
  105.         for (int j = 0; j < start.size(); ++j) {
  106.             string s;
  107.             int now = start[j];
  108.             deque<int> d;
  109.             for (int q = 0; q < i; ++q) {
  110.                 s = obr[now].second + s;
  111.                 d.push_front(now);
  112.                 now = obr[now].first;
  113.             }
  114.             d.push_front(now);
  115.             auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
  116.             if (it_1 != mer.end() && it_1 == --it_2) {
  117.                 for (int c = 0; c < d.size() - 1; ++c) {
  118.                     if (kl[*it_1] < dp[d[c]][d[c + 1]]) {
  119.                         pr[d[c]][d[c + 1]].first = d.front();
  120.                         pr[d[c]][d[c + 1]].second = d.back();
  121.                         dp[d[c]][d[c + 1]] = kl[*it_1];
  122.                         tok[d[c]][d[c + 1]] = num[*it_1];
  123.                     }
  124.                 }
  125.             }
  126.  
  127.             while (d[0] != 1) {
  128.                 s.pop_back();
  129.                 s = obr[now].second + s;
  130.                 d.pop_back();
  131.                 now = obr[now].first;
  132.                 d.push_front(now);
  133.                 auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
  134.                 if (it_1 != mer.end() && it_1 == --it_2) {
  135.                     for (int c = 0; c < d.size() - 1; ++c) {
  136.                         if (kl[*it_1] < dp[d[c]][d[c + 1]]) {
  137.                             pr[d[c]][d[c + 1]].first = d.front();
  138.                             pr[d[c]][d[c + 1]].second = d.back();
  139.                             dp[d[c]][d[c + 1]] = kl[*it_1];
  140.                             tok[d[c]][d[c + 1]] = num[*it_1];
  141.                         }
  142.                     }
  143.                 }
  144.             }
  145.         }
  146.     }
  147.     used.resize(n + 1, 1);
  148.     dfs(pr, dp, g, obr, tok, 1);
  149.     if (sum > 1e17) {
  150.         cout << -1;
  151.     } else {
  152.         cout << sum;
  153.         if (t == 1) {
  154.             cout << "\n" << answer.size() << "\n";
  155.             for (int i  = 0; i < answer.size(); ++i) {
  156.                 cout << answer[i].first.first << " " << answer[i].first.second << " " << answer[i].second << "\n";
  157.             }
  158.         }
  159.     }
  160.  
  161.     return 0;
  162. }
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
 
Top