Submission #914629

#TimeUsernameProblemLanguageResultExecution timeMemory
914629minhnhatnoeWorst Reporter 4 (JOI21_worst_reporter4)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 20; int a[MAXN], h[MAXN], c[MAXN], deg[MAXN], n; map<int, long long> s[MAXN]; vector<int> q; void cdeg(int v){ if (deg[v]) return; auto it = s[v].lower_bound(h[v]); if (it == s[v].end() || it->first != h[v]) it = s[v].emplace_hint(it, h[v], 0); it->second += c[v]; for (int x = c[v]; it != s[v].begin() && x;){ it--; if (it->second <= x){ x -= it->second; it = s[v].erase(it); } else{ it->second -= x; x = 0; } } q.push_back(v); } void merge(map<int, long long> &a, map<int, long long> &b){ if (a.size() < b.size()) swap(a, b); a.merge(b); } long long pfm(map<int, long long> &hs){ long long p = 0; for (auto it = hs.rbegin(); it != hs.rend(); it++) p = it->second = p + it->second; hs.emplace_hint(hs.end(), INT_MAX, 0); return p; } signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i=0; i<n; i++){ cin >> a[i] >> h[i] >> c[i]; a[i]--, deg[a[i]]++; } for (int i=0; i<n; i++) cdeg(i); long long result = accumulate(c, c + n, 0LL); while (q.size()){ int v = q.back(); q.pop_back(); merge(s[a[v]], s[v]); deg[a[v]]--, cdeg(a[v]); } for (int i=0; i<n; i++){ if (!deg[i]) continue; vector<pair<int, long long>> ss; map<int, long long> hs; for (int pos = i; deg[pos]; deg[pos] = 0, pos = a[pos]){ merge(hs, s[pos]); ss.emplace_back(h[pos], c[pos]); } sort(ss.begin(), ss.end()); long long max_branch = pfm(hs); for (int lptr=0, rptr=0; lptr<ss.size(); lptr=rptr){ long long v = hs.lower_bound(ss[lptr].first)->second; for (; rptr < ss.size() && ss[lptr].first == ss[rptr].first; rptr++) v += ss[rptr].second; max_branch = max(max_branch, v); } result -= max_branch; } cout << result << "\n"; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:70:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int lptr=0, rptr=0; lptr<ss.size(); lptr=rptr){
      |                                  ~~~~^~~~~~~~~~
worst_reporter2.cpp:72:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (; rptr < ss.size() && ss[lptr].first == ss[rptr].first; rptr++)
      |                    ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...