Submission #1147161

#TimeUsernameProblemLanguageResultExecution timeMemory
1147161ElayV13Bosses (BOI16_bosses)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(a) a.begin() , a.end()

const int INF = 1e18;
const int MAX = 5e3 + 5;
const int mod = 998244353;

vector < int > read(string s)
{
      string cur = "";
      vector < int > res;
      for(int i = 0;i < s.size();i++){
            if(s[i] != ' '){
                  cur = cur + s[i];
            }
            else{
                  res.push_back(stoll(cur));
                  cur = "";
            }
      }
      if(cur.size()) res.push_back(stoll(cur));
      return res;
}

int mp[MAX] , req[MAX];

void solve()
{
      int n;
      cin >> n;
      cin.ignore();
      vector < vector < int > > a(n + 1);
      for(int i = 1;i <= n;i++)
      {
            string boss;
            getline(cin , boss);
            a[i] = read(boss);
      }
      for(int i = 1;i <= n;i++){
            for(int u : a[i]){
                  mp[u]++;
            }
      }
      vector < pair < int , int > > dd;
      for(int i = 1;i <= n;i++){
            dd.push_back({mp[i] , i});
      }
      sort(all(dd));
      vector < int > emp;
      for(pair < int , int > pp : dd){
            emp.push_back(pp.first);
      }
      req[emp[0]] = 1;
      int sum = 0;
      for(int i = 0;i < emp.size();i++){
            if(req[emp[i]] == 0){
                  req[emp[i]] = sum;
            }
            sum += req[emp[i]];
      }
      int res = 0;
      for(int i = 0;i < emp.size();i++){
            res += req[emp[i]];
      }
      cout << res << endl;
}

signed main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);
      int T = 1;
      //cin >> T;
      while(T--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...