oj.uz

답안 #786691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786691 2023-07-18T11:21:00 Z PoonYaPat Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 214 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n,p[200005],h[400005];
ll val[200005],Ans;
vector<int> adj[200005],adj2[400005],v[400005];
set<ll> ss[400005];
map<ll,ll> temp[400005];
bool mark[200005],vis[200005];
stack<int> st;

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

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

    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);
        }
    }

    if (x<3*n) {
        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;
                }
            }
        }

        Ans=temp[x][0];

    } else {
        
        for (auto s : v[x]) {
            temp[x][0]+=val[s]; ss[x].insert(0);
            temp[x][h[s]]-=val[s]; ss[x].insert(h[s]);
            temp[x][h[s]+1]+=val[s]; ss[x].insert(h[s]+1);
        }

        ll sum=0;
        Ans=LLONG_MAX;

        for (auto s : ss[x]) {
            sum+=temp[x][s];
            Ans=min(Ans,sum);
        }

    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("sample-03-in.txt","r",stdin);
    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]) {
            int x=i;
            dfs1(x);
            while (!vis[p[x]]) {
                x=p[x];
                dfs1(x);
            }

            int idx=p[x];
            while (idx!=x) {
                mark[idx]=true;
                v[n+x].push_back(idx);
                idx=p[idx];
            }
            mark[x]=true;
            v[n+x].push_back(x);

            assert(v[n+x].size()==1);

            while (st.size()) {
                int node=st.top();
                st.pop();
                if (mark[node]) for (auto s : adj[node]) {
                    if (mark[s]) continue;
                    if (node==p[x] && s==x) continue;
                    adj2[n+x].push_back(s);
                    assert(node==x);
                } else for (auto s : adj[node]) adj2[node].push_back(s);
            }

            assert(Ans==0);

            dfs2(x);
            ans+=Ans;
        }
    }
    cout<<ans;
}

Compilation message

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

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -