bosses.cpp

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vpii = vector<pii>;

#define rep(x, s, e) for (int x = (int)s; x < (int)e; ++x)

vector<vi> e;

vector<vi> g;
ll cost(int cur, ll& total) {
  ll salary = 1;
  for (int u : g[cur]) salary += cost(u, total);
  total += salary;
  return salary;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  if (n > 100) return 0;

  e.resize(n);
  rep(i, 0, n) {
    int x;
    cin >> x;
    rep(j, 0, x) {
      int boss;
      cin >> boss;
      boss--;
      e[boss].push_back(i);
    }
  }

  long long cheapest = 1e18;
  queue<int> q;
  rep(start, 0, n) {
    g.assign(n, vi());
    q.push(start);
    vector<int> vis(n, false);
    vis[start] = true;
    int left = n - 1;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int u : e[cur])
        if (!vis[u]) {
          vis[u] = true;
          left--;
          g[cur].push_back(u);
          q.push(u);
        }
    }
    if (left == 0) {
      ll total = 0;
      cost(start, total);
      cheapest = min(cheapest, total);
    }
  }

  cout << cheapest << endl;

  return 0;
}

friends.cpp

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vpii = vector<pii>;

#define rep(x, s, e) for (int x = (int)s; x < (int)e; ++x)

int n;
string s;

bool check(string x, int start) {
  // cout << x << " " << start << endl;
  int wrong = 0;
  for (int i = 0; i < x.size(); ++i) {
    // cout << x[i] << " " << s[i + start + wrong] << " " << i << " "
    //      << i + start + wrong << endl;
    if (x[i] != s[i + start + wrong]) {
      if (wrong == 1)
        return false;
      else {
        wrong++;
        i--;
      }
    }
  }
  return true;
}

int main() {
  cin >> n;
  cin >> s;

  if (n % 2 == 0) {
    cout << "NOT POSSIBLE" << endl;
    return 0;
  }

  string a = s.substr(0, n / 2);
  string b = s.substr(n - n / 2, n / 2);

  bool ok1 = check(a, n / 2);
  bool ok2 = check(b, 0);

  if (ok1 && ok2 && a != b)
    cout << "NOT UNIQUE" << endl;
  else if (ok1)
    cout << a << endl;
  else if (ok2)
    cout << b << endl;
  else
    cout << "NOT POSSIBLE" << endl;

  return 0;
}