이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200000;
int a[MAXN], h[MAXN], c[MAXN], deg[MAXN], n;
map<int, long long> s[MAXN];
vector<int> q;
// dp(v, i) =
// h[v] < i: \sum{dp(u, i)}
// h[v] >= i: max(\sum{dp(u, i)}, c[v] + \sum{dp(u, h[v])})
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, int>> cyc;
map<int, long long> hs;
for (int pos = i; deg[pos]; deg[pos] = 0, pos = a[pos]){
merge(hs, s[pos]);
cyc.emplace_back(h[pos], c[pos]);
}
sort(cyc.begin(), cyc.end());
long long max_branch = pfm(hs);
for (int lptr=0, rptr=0; lptr<cyc.size(); lptr=rptr){
long long v = hs.lower_bound(cyc[lptr].first)->second;
for (; rptr < cyc.size() && cyc[lptr].first == cyc[rptr].first; rptr++)
v += cyc[rptr].second;
max_branch = max(max_branch, v);
}
result -= max_branch;
}
cout << result << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:76:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int lptr=0, rptr=0; lptr<cyc.size(); lptr=rptr){
| ~~~~^~~~~~~~~~~
worst_reporter2.cpp:78:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (; rptr < cyc.size() && cyc[lptr].first == cyc[rptr].first; rptr++)
| ~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |