Submission #786594

#	Time	Username	Problem	Language	Result	Execution time	Memory
786594		PoonYaPat	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	634 ms	198688 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n,p[200005],h[200005];
ll val[200005];
vector<int> adj[200005];
set<ll> ss[200005];
map<ll,ll> temp[200005];
bool mark[200005],vis[200005];

void dfs1(int x) {
    vis[x]=true;
    for (auto s : adj[x]) if (!vis[s]) dfs1(s);
}

void dfs2(int x) {
    for (auto s : adj[x]) dfs2(s);

    if (!mark[x]) {
        if (adj[x].size()) {
            swap(ss[x],ss[adj[x][0]]);
            swap(temp[x],temp[adj[x][0]]);

            for (int i=1; i<adj[x].size(); ++i) {
                int c=adj[x][i];
                if (ss[c].size()>ss[x].size()) swap(temp[x],temp[c]), swap(ss[x],ss[c]);

                for (auto s : ss[c]) temp[x][s]+=temp[c][s], ss[x].insert(s);
            }
        }

        temp[x][0]+=val[x]; ss[x].insert(0);
        temp[x][h[x]]-=val[x]; ss[x].insert(h[x]);
        temp[x][h[x]+1]+=val[x]; ss[x].insert(h[x]+1);

        if (temp[x][h[x]]<0) {
            ll k=-temp[x][h[x]];
            auto it=ss[x].find(h[x]);

            temp[x][h[x]]=0;
            auto h=it; --it;
            ss[x].erase(h);

            while (true) {
                if (temp[x][*it]<k) {
                    k-=temp[x][*it];
                    temp[x][*it]=0;
                    auto h=it; --it;
                    ss[x].erase(h);
                } else {
                    temp[x][*it]-=k;
                    if (temp[x][*it]==0) ss[x].erase(it);
                    break;
                }
            }
        }
    } else {
        ss[x].insert(0);
        temp[x][0]=val[x];
        for (auto s : adj[x]) temp[x][0]+=temp[s][0];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        cin>>p[i]>>h[i]>>val[i];
        adj[p[i]].push_back(i);
    }

    ll ans=0;
    for (int i=1; i<=n; ++i) {
        if (!vis[i]) {
            dfs1(i);
            while (!vis[p[i]]) {
                i=p[i];
                dfs1(i);
            }

            for (int j=0; j<adj[p[i]].size(); ++j) {
                if (adj[p[i]][j]==i) {
                    swap(adj[p[i]][j],adj[p[i]].back());
                    adj[p[i]].pop_back();
                    break;
                }
            }

            int idx=p[i];
            bool same=true;
            while (idx!=i) {
                if (val[idx]!=val[i]) same=false;
                idx=p[idx];
            }
            
            if (!same) {
                idx=p[i];
                while (idx!=i) {
                    mark[idx]=true;
                    idx=p[idx];
                }
                mark[i]=true;
            }

            dfs2(i);
            ans+=temp[i][0];
        }
    }
    cout<<ans;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs2(int)':
worst_reporter2.cpp:26:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int i=1; i<adj[x].size(); ++i) {
      |                           ~^~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:83:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int j=0; j<adj[p[i]].size(); ++j) {
      |                           ~^~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21