Submission #846016

#	Time	Username	Problem	Language	Result	Execution time	Memory
846016		MKutayBozkurt	Trener (COCI20_trener)	C++17	110 / 110	143 ms	13216 KiB

trener

/**
 *  author: kututay
 *  created: 06.09.2023 16:41:38
**/
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
  #include "/Users/kutay/CP/templates/debug.h"
#else
  #define debug(...) void(38)
#endif

#define int long long

const int mod = 1e9 + 7;

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, k; cin >> n >> k;
  vector<vector<int>> a(n * k + 2);
  vector<int> dp(n * k + 2, -1), cnt(n * k + 2);

  function<int(int)> f = [&](int node) {
    if (dp[node] != -1) return dp[node];
    int res = 0;
    sort(a[node].begin(), a[node].end());
    for (int i = 0; i < (int) a[node].size(); i++) {
      int next = a[node][i];
      if (i > 0 && a[node][i - 1] == next) continue;
      res += (cnt[node] * f(next)) % mod;
      res %= mod;
    }
    return dp[node] = res;
  };

  map<string, int> m;
  int count = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      string s; cin >> s;
      if (m.count(s) == 0) {
        m[s] = ++count;
      }
      int node = m[s];
      cnt[node]++;
      if (i == n - 1) dp[node] = cnt[node];
      if (i > 0) {
        if (m.count(s.substr(0, i))) a[m[s.substr(0, i)]].emplace_back(node);
        if (m.count(s.substr(1, i))) a[m[s.substr(1, i)]].emplace_back(node);
      } else {
        if (cnt[node] == 1) {
          a[n * k + 1].emplace_back(node);
        }
      }
    }
  }
  cnt[n * k + 1] = 1;
  cout << f(n * k + 1) << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55