oj.uz

Submission #805293

# Submission time Handle Problem Language Result Execution time Memory
805293 2023-08-03T14:53:17 Z bachhoangxuan Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 957 ms 524288 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=200005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

void solve(){
    int n;cin >> n;
    vector<int> a(n+1),c(n+1),h(n+1),deg(n+1,0);
    vector<vector<int>> child(n+1);
    vector<map<int,int>> mp(n+1);

    for(int i=1;i<=n;i++){
        cin >> a[i] >> h[i] >> c[i];
        child[a[i]].push_back(i);deg[a[i]]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++) if(deg[i]==0) q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        deg[a[u]]--;
        if(deg[a[u]]==0) q.push(a[u]);
    }
    auto unions = [&](int u,int v){
        if((int)mp[u].size()>(int)mp[v].size()) swap(mp[u],mp[v]);
        for(auto [x,val]:mp[v]) mp[u][x]+=val;
    };
    function<void(int)> dfs = [&](int u){
        for(int v:child[u]) dfs(v),unions(u,v);
        mp[u][0]+=c[u];
        int cur=h[u],del=c[u];
        auto it=mp[u].upper_bound(h[u]);
        while(it!=mp[u].begin()){
            it--;
            if(it->se<=del) del-=it->se,it=mp[u].erase(it);
            else{mp[u][it->fi]-=del;break;}
        }
        mp[u][h[u]+1]+=c[u];
    };

    int total=0;
    for(int i=1;i<=n;i++){
        if(deg[i]){
            int u=i,sum=0;
            vector<pii> cc,nw;
            do{
                cc.push_back({h[u],u});sum+=c[u];
                for(int v:child[u]) if(!deg[v]) dfs(v),unions(i,v);
                u=a[u];
            }while(u!=i);
            sort(cc.begin(),cc.end());
            for(auto [x,u]:cc) deg[u]=0;
            for(auto [x,u]:cc){
                if(nw.empty() || nw.back().fi!=x) nw.push_back({x,c[u]});
                else nw.back().se+=c[u];
            }
            cc.clear();
            for(auto [x,val]:mp[i]) cc.push_back({x,val});
            int pos=0,cur=0,res=sum+mp[i][0];
            for(auto [x,val]:nw){
                while(pos<(int)cc.size() && cc[pos].fi<=x) cur+=cc[pos++].se;
                res=min(res,cur+sum-val);
            }
            total+=res;

        }
    }
    cout << total << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Compilation message

worst_reporter2.cpp: In lambda function:
worst_reporter2.cpp:77:13: warning: unused variable 'cur' [-Wunused-variable]
   77 |         int cur=h[u],del=c[u];
      |             ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 26 ms 11996 KB Output is correct
6 Correct 10 ms 4300 KB Output is correct
7 Correct 5 ms 2336 KB Output is correct
8 Correct 20 ms 8872 KB Output is correct
9 Correct 9 ms 4176 KB Output is correct
10 Correct 6 ms 2316 KB Output is correct
11 Correct 3 ms 1348 KB Output is correct
12 Correct 76 ms 42352 KB Output is correct
13 Correct 10 ms 4940 KB Output is correct
14 Correct 67 ms 29436 KB Output is correct
15 Correct 30 ms 15940 KB Output is correct
16 Correct 9 ms 4052 KB Output is correct
17 Correct 6 ms 2772 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 957 ms 450016 KB Output is correct
20 Correct 58 ms 31504 KB Output is correct
21 Correct 5 ms 3156 KB Output is correct
22 Runtime error 753 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 26 ms 11996 KB Output is correct
6 Correct 10 ms 4300 KB Output is correct
7 Correct 5 ms 2336 KB Output is correct
8 Correct 20 ms 8872 KB Output is correct
9 Correct 9 ms 4176 KB Output is correct
10 Correct 6 ms 2316 KB Output is correct
11 Correct 3 ms 1348 KB Output is correct
12 Correct 76 ms 42352 KB Output is correct
13 Correct 10 ms 4940 KB Output is correct
14 Correct 67 ms 29436 KB Output is correct
15 Correct 30 ms 15940 KB Output is correct
16 Correct 9 ms 4052 KB Output is correct
17 Correct 6 ms 2772 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 957 ms 450016 KB Output is correct
20 Correct 58 ms 31504 KB Output is correct
21 Correct 5 ms 3156 KB Output is correct
22 Runtime error 753 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 26 ms 11996 KB Output is correct
6 Correct 10 ms 4300 KB Output is correct
7 Correct 5 ms 2336 KB Output is correct
8 Correct 20 ms 8872 KB Output is correct
9 Correct 9 ms 4176 KB Output is correct
10 Correct 6 ms 2316 KB Output is correct
11 Correct 3 ms 1348 KB Output is correct
12 Correct 76 ms 42352 KB Output is correct
13 Correct 10 ms 4940 KB Output is correct
14 Correct 67 ms 29436 KB Output is correct
15 Correct 30 ms 15940 KB Output is correct
16 Correct 9 ms 4052 KB Output is correct
17 Correct 6 ms 2772 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 957 ms 450016 KB Output is correct
20 Correct 58 ms 31504 KB Output is correct
21 Correct 5 ms 3156 KB Output is correct
22 Runtime error 753 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -