#ifdef local
#define debug(x) cout<<#x<<" "<<x<<endl;
#else
#define debug(x)
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const ll mod=1e9+7,lim=25+5,bitlim=15,inf=1e9;
vector<ll>adjl[lim],adjl2[lim];
ll pwr[lim],cost[lim],nxt[lim],cyc[lim],vis[lim],a[lim],direc[lim];
map<ll,ll> *mps[lim];
vector<vector<ll> >cycs;
bool bruh[lim];
void dp(ll pos){
if(adjl[pos].size() == 0){
mps[pos] = new map<ll,ll>();
mps[pos]->operator[](0)=0;
mps[pos]->operator[](pwr[pos] + 1) = cost[pos];
}
else{
ll maxsz=0,maxszidx=0;
for(int i=0;i<adjl[pos].size();i++){
ll u=adjl[pos][i];
dp(u);
if(mps[u]->size()>maxsz){
maxsz=mps[u]->size();
maxszidx=u;
}
}
mps[pos] = mps[maxszidx];
for(int i=0;i<adjl[pos].size();i++){
ll u=adjl[pos][i];
if(u==maxszidx)continue;
for(auto p:*mps[u]){
ll k,v;
tie(k,v)=p;
mps[pos]->operator[](k)+=v;
}
}
mps[pos]->operator[](0) += cost[pos];
mps[pos]->operator[](pwr[pos] + 1) += cost[pos];
auto it=mps[pos]->upper_bound(pwr[pos]);
ll rem=cost[pos];
while(rem>0){
it--;
if(rem<=it->second)it->second-=rem,rem=0;
else rem-=it->second,it=mps[pos]->erase(it);
}
}
return;
}
ll dfs(ll pos,ll idx){
vis[pos]=idx;
if(vis[nxt[pos]]==-1){
ll k = dfs(nxt[pos],idx);
if(k!=-1){
cyc[pos]=idx;
cycs.back().push_back(pos);
if(k!=pos)return k;
}
return -1;
}
else if(vis[nxt[pos]]==idx){
cyc[pos]=idx;
cycs.push_back(vector<ll>());
cycs.back().push_back(pos);
if(nxt[pos]==pos)return -1;
else return nxt[pos];
}
else return -1;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(NULL);
ll n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>pwr[i]>>cost[i];
nxt[i]=a[i];
}
fill(vis,vis+lim,-1);
for(int i=0;i<=n;i++)cyc[i]=-(i+1);
for(int i=1;i<=n;i++){
if(vis[i]==-1)dfs(i,i);
}
ll ans=0;
vector<ll>roots;
fill(direc,direc+lim,-1);
for(auto x:cycs){
ll mnpos,mnpwr=1e18;
sort(x.begin(),x.end(),[](ll a,ll b){
return pwr[a]>pwr[b];
});
// cout<<"CYC: ";
// for(auto y:x)cout<<y<<" ";
// cout<<"\n";
for(int i=1;i<x.size();i++){
a[x[i]]=x[i-1];
direc[x[i]]=x[0];
bruh[x[i]]=1;
}
a[x[0]]=x[0];
roots.push_back(x[0]);
}
for(int i=1;i<=n;i++){
if(i!=a[i]){
if(direc[a[i]]!=-1&&bruh[i]==0)adjl[direc[a[i]]].push_back(i);
else adjl[a[i]].push_back(i);
}
}
// for(int i=1;i<=n;i++)cout<<i<<": "<<cyc[i]<<"\n";
//cout<<ans;
for(auto x:roots){
dp(x);
ans+=(mps[x]->begin())->second;//<<"\n";
// cout<<"x: "<<x<<": "<<(mps[x]->begin())->first<<" "<<(mps[x]->begin())->second<<"\n";
}
cout<<ans<<"\n";
for(int i=1;i<=n;i++){
// cout<<i<<": ";
// for(auto x:adjl[i])cout<<x<<" ";
// cout<<"\n";
}
// dp(1);
// cout<<mps[1]->begin()->second<<"\n";
return 0;
}
/*
5
2 25 55
3 20 42
4 30 69
1 28 39
1 27 50
20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030*/
Compilation message
worst_reporter2.cpp: In function 'void dp(ll)':
worst_reporter2.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<adjl[pos].size();i++){
| ~^~~~~~~~~~~~~~~~~
worst_reporter2.cpp:28:21: warning: comparison of integer expressions of different signedness: 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
28 | if(mps[u]->size()>maxsz){
| ~~~~~~~~~~~~~~^~~~~~
worst_reporter2.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<adjl[pos].size();i++){
| ~^~~~~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=1;i<x.size();i++){
| ~^~~~~~~~~
worst_reporter2.cpp:94:6: warning: unused variable 'mnpos' [-Wunused-variable]
94 | ll mnpos,mnpwr=1e18;
| ^~~~~
worst_reporter2.cpp:94:12: warning: unused variable 'mnpwr' [-Wunused-variable]
94 | ll mnpos,mnpwr=1e18;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
