oj.uz

Submission #1080817

# Submission time Handle Problem Language Result Execution time Memory
1080817 2024-08-29T14:33:23 Z 8pete8 Worst Reporter 4 (JOI21_worst_reporter4) C++17
100 / 100
 387 ms 125520 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30,valbound=1e9;
//#undef int
int n,k,m,q;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int go[mxn+10],val[mxn+10],cost[mxn+10],p[mxn+10],deg[mxn+10];
vector<int>adj[mxn+10],have[mxn+10];
int vis[mxn+10],pa[mxn+10],on[mxn+10];;
stack<int>st;
int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
void merg(int a,int b){
    a=find(a),b=find(b);
    if(a==b)return;
    pa[a]=b;
}
void dfs(int cur){
    vis[cur]=on[cur]=1;
    st.push(cur);
    if(!vis[go[cur]])dfs(go[cur]);
    else if(on[go[cur]]){
        while(!st.empty()&&st.top()!=go[cur]){
            merg(cur,st.top());
            st.pop();
        }
        if(!st.empty()){
            merg(cur,st.top());
            st.pop();
        }
    }
    on[cur]=0;
}
map<int,int>dp[mxn+10];
//keep prefix sum
//like magic tree?
//can also do merge segtree
void solve(int cur,int root){
    for(auto i:adj[cur]){
        solve(i,0);
        if(dp[i].size()>dp[cur].size())swap(dp[cur],dp[i]);
        for(auto j:dp[i])dp[cur][j.f]+=j.s;
    }
    if(!root){
        dp[cur][val[cur]]+=cost[cur];
        auto it=(dp[cur].find(val[cur]));
        if(it!=dp[cur].begin()){
            it=prev(it);
            while(cost[cur]){
                if(cost[cur]>=it->s){
                    cost[cur]-=it->s;
                    it=dp[cur].erase(it);
                    if(it==dp[cur].begin())break;
                    it=prev(it);
                }
                else it->s-=cost[cur],cost[cur]=0;
            }
        }
    }
}
int sum=0;
int32_t main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>go[i]>>val[i]>>cost[i],pa[i]=i,sum+=cost[i];
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            while(!st.empty())st.pop();
        }
    }
    for(int i=1;i<=n;i++)have[find(i)].pb(i);
    for(int i=1;i<=n;i++)if(find(go[i])!=find(i)){
        adj[find(go[i])].pb(find(i));
        deg[find(i)]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(find(i)==i&&deg[i]==0){
        solve(i,1);
        map<int,int>cnt;
        for(auto j:have[i])cnt[val[j]]+=cost[j];
        int mx=0,cursum=0,can=1;
        auto it=(dp[i].end());
        if(it==dp[i].begin())can=0;
        else it=prev(it);
        auto j=prev(cnt.end());
        while(1){
            while(can&&it->f>=j->f){
                cursum+=it->s;
                if(it==dp[i].begin())can=0;
                it--;
            }
            mx=max(mx,cursum+j->s);
            if(j==cnt.begin())break;
            j--;
        }
        while(can){
            cursum+=it->s;
            if(it==dp[i].begin())can=0;
            it--;
        }
        mx=max(mx,cursum);
        ans+=mx;
    }
    cout<<sum-ans<<'\n';
}
/*
create graph
one cycle per comp
will be a line with cycle at the end
if we have a cycle then every node of that cycle should have the same value
we will have a forest
then we can just get min cost decreasing sequence
*/

Compilation message

worst_reporter2.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
worst_reporter2.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
worst_reporter2.cpp:47:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 | int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
      |               ^
worst_reporter2.cpp:48:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | void merg(int a,int b){
      |                      ^
worst_reporter2.cpp:53:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 | void dfs(int cur){
      |                 ^
worst_reporter2.cpp:73:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | void solve(int cur,int root){
      |                            ^
worst_reporter2.cpp:97:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   97 | int32_t main(){
      |              ^
worst_reporter2.cpp: In function 'void setIO(std::string)':
worst_reporter2.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 7 ms 31172 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 10 ms 32680 KB Output is correct
6 Correct 9 ms 32092 KB Output is correct
7 Correct 9 ms 30044 KB Output is correct
8 Correct 10 ms 30556 KB Output is correct
9 Correct 8 ms 32148 KB Output is correct
10 Correct 8 ms 30040 KB Output is correct
11 Correct 8 ms 29788 KB Output is correct
12 Correct 9 ms 30508 KB Output is correct
13 Correct 9 ms 26456 KB Output is correct
14 Correct 8 ms 26204 KB Output is correct
15 Correct 8 ms 27992 KB Output is correct
16 Correct 17 ms 32860 KB Output is correct
17 Correct 9 ms 32344 KB Output is correct
18 Correct 7 ms 23752 KB Output is correct
19 Correct 8 ms 32348 KB Output is correct
20 Correct 8 ms 30044 KB Output is correct
21 Correct 11 ms 32272 KB Output is correct
22 Correct 8 ms 26144 KB Output is correct
23 Correct 7 ms 23896 KB Output is correct
24 Correct 8 ms 26456 KB Output is correct
25 Correct 13 ms 32092 KB Output is correct
26 Correct 8 ms 24412 KB Output is correct
27 Correct 9 ms 32348 KB Output is correct
28 Correct 8 ms 30580 KB Output is correct
29 Correct 8 ms 32668 KB Output is correct
30 Correct 9 ms 32604 KB Output is correct
31 Correct 9 ms 30476 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 7 ms 31172 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 10 ms 32680 KB Output is correct
6 Correct 9 ms 32092 KB Output is correct
7 Correct 9 ms 30044 KB Output is correct
8 Correct 10 ms 30556 KB Output is correct
9 Correct 8 ms 32148 KB Output is correct
10 Correct 8 ms 30040 KB Output is correct
11 Correct 8 ms 29788 KB Output is correct
12 Correct 9 ms 30508 KB Output is correct
13 Correct 9 ms 26456 KB Output is correct
14 Correct 8 ms 26204 KB Output is correct
15 Correct 8 ms 27992 KB Output is correct
16 Correct 17 ms 32860 KB Output is correct
17 Correct 9 ms 32344 KB Output is correct
18 Correct 7 ms 23752 KB Output is correct
19 Correct 8 ms 32348 KB Output is correct
20 Correct 8 ms 30044 KB Output is correct
21 Correct 11 ms 32272 KB Output is correct
22 Correct 8 ms 26144 KB Output is correct
23 Correct 7 ms 23896 KB Output is correct
24 Correct 8 ms 26456 KB Output is correct
25 Correct 13 ms 32092 KB Output is correct
26 Correct 8 ms 24412 KB Output is correct
27 Correct 9 ms 32348 KB Output is correct
28 Correct 8 ms 30580 KB Output is correct
29 Correct 8 ms 32668 KB Output is correct
30 Correct 9 ms 32604 KB Output is correct
31 Correct 9 ms 30476 KB Output is correct
32 Correct 10 ms 32632 KB Output is correct
33 Correct 328 ms 100944 KB Output is correct
34 Correct 260 ms 76288 KB Output is correct
35 Correct 387 ms 98132 KB Output is correct
36 Correct 259 ms 76116 KB Output is correct
37 Correct 204 ms 57364 KB Output is correct
38 Correct 175 ms 52720 KB Output is correct
39 Correct 204 ms 80724 KB Output is correct
40 Correct 224 ms 80724 KB Output is correct
41 Correct 192 ms 80464 KB Output is correct
42 Correct 198 ms 65108 KB Output is correct
43 Correct 194 ms 65104 KB Output is correct
44 Correct 329 ms 125520 KB Output is correct
45 Correct 259 ms 89940 KB Output is correct
46 Correct 155 ms 52304 KB Output is correct
47 Correct 269 ms 74832 KB Output is correct
48 Correct 187 ms 67924 KB Output is correct
49 Correct 163 ms 67920 KB Output is correct
50 Correct 271 ms 68800 KB Output is correct
51 Correct 164 ms 56512 KB Output is correct
52 Correct 279 ms 75968 KB Output is correct
53 Correct 185 ms 68968 KB Output is correct
54 Correct 208 ms 80892 KB Output is correct
55 Correct 211 ms 77372 KB Output is correct
56 Correct 201 ms 83284 KB Output is correct
57 Correct 200 ms 86612 KB Output is correct
58 Correct 237 ms 83108 KB Output is correct
59 Correct 237 ms 83024 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 7 ms 31172 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 10 ms 32680 KB Output is correct
6 Correct 9 ms 32092 KB Output is correct
7 Correct 9 ms 30044 KB Output is correct
8 Correct 10 ms 30556 KB Output is correct
9 Correct 8 ms 32148 KB Output is correct
10 Correct 8 ms 30040 KB Output is correct
11 Correct 8 ms 29788 KB Output is correct
12 Correct 9 ms 30508 KB Output is correct
13 Correct 9 ms 26456 KB Output is correct
14 Correct 8 ms 26204 KB Output is correct
15 Correct 8 ms 27992 KB Output is correct
16 Correct 17 ms 32860 KB Output is correct
17 Correct 9 ms 32344 KB Output is correct
18 Correct 7 ms 23752 KB Output is correct
19 Correct 8 ms 32348 KB Output is correct
20 Correct 8 ms 30044 KB Output is correct
21 Correct 11 ms 32272 KB Output is correct
22 Correct 8 ms 26144 KB Output is correct
23 Correct 7 ms 23896 KB Output is correct
24 Correct 8 ms 26456 KB Output is correct
25 Correct 13 ms 32092 KB Output is correct
26 Correct 8 ms 24412 KB Output is correct
27 Correct 9 ms 32348 KB Output is correct
28 Correct 8 ms 30580 KB Output is correct
29 Correct 8 ms 32668 KB Output is correct
30 Correct 9 ms 32604 KB Output is correct
31 Correct 9 ms 30476 KB Output is correct
32 Correct 10 ms 32632 KB Output is correct
33 Correct 328 ms 100944 KB Output is correct
34 Correct 260 ms 76288 KB Output is correct
35 Correct 387 ms 98132 KB Output is correct
36 Correct 259 ms 76116 KB Output is correct
37 Correct 204 ms 57364 KB Output is correct
38 Correct 175 ms 52720 KB Output is correct
39 Correct 204 ms 80724 KB Output is correct
40 Correct 224 ms 80724 KB Output is correct
41 Correct 192 ms 80464 KB Output is correct
42 Correct 198 ms 65108 KB Output is correct
43 Correct 194 ms 65104 KB Output is correct
44 Correct 329 ms 125520 KB Output is correct
45 Correct 259 ms 89940 KB Output is correct
46 Correct 155 ms 52304 KB Output is correct
47 Correct 269 ms 74832 KB Output is correct
48 Correct 187 ms 67924 KB Output is correct
49 Correct 163 ms 67920 KB Output is correct
50 Correct 271 ms 68800 KB Output is correct
51 Correct 164 ms 56512 KB Output is correct
52 Correct 279 ms 75968 KB Output is correct
53 Correct 185 ms 68968 KB Output is correct
54 Correct 208 ms 80892 KB Output is correct
55 Correct 211 ms 77372 KB Output is correct
56 Correct 201 ms 83284 KB Output is correct
57 Correct 200 ms 86612 KB Output is correct
58 Correct 237 ms 83108 KB Output is correct
59 Correct 237 ms 83024 KB Output is correct
60 Correct 5 ms 31320 KB Output is correct
61 Correct 5 ms 29272 KB Output is correct
62 Correct 4 ms 31324 KB Output is correct
63 Correct 4 ms 29276 KB Output is correct
64 Correct 315 ms 85844 KB Output is correct
65 Correct 254 ms 69148 KB Output is correct
66 Correct 302 ms 86608 KB Output is correct
67 Correct 280 ms 69024 KB Output is correct
68 Correct 212 ms 55320 KB Output is correct
69 Correct 187 ms 51796 KB Output is correct
70 Correct 232 ms 60108 KB Output is correct
71 Correct 170 ms 48724 KB Output is correct
72 Correct 235 ms 69704 KB Output is correct
73 Correct 181 ms 59216 KB Output is correct
74 Correct 234 ms 69576 KB Output is correct
75 Correct 197 ms 57288 KB Output is correct
76 Correct 170 ms 57036 KB Output is correct
77 Correct 245 ms 69576 KB Output is correct
78 Correct 179 ms 57292 KB Output is correct
79 Correct 300 ms 85268 KB Output is correct
80 Correct 246 ms 68168 KB Output is correct
81 Correct 230 ms 57452 KB Output is correct
82 Correct 252 ms 69964 KB Output is correct
83 Correct 175 ms 43092 KB Output is correct
84 Correct 384 ms 65160 KB Output is correct
85 Correct 311 ms 65308 KB Output is correct
86 Correct 304 ms 62052 KB Output is correct
87 Correct 257 ms 66272 KB Output is correct
88 Correct 309 ms 68624 KB Output is correct