제출 #899679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899679		LucaIlie	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	492 ms	100828 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
int n;
bool vis[MAX_N + 1];
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1], sc[MAX_N + 1];
vector <int> edges[MAX_N + 1], children[MAX_N + 1];
map <int, long long> inc[MAX_N + 1];

void computeDP( int u ) {
    sc[u] = cost[u];
    for ( int v: children[u] ) {
        computeDP( v );
        sc[u] += sc[v];
    }

    int maxSize = 0, h = -1;
    for ( int v: children[u] ) {
        if ( inc[v].size() > maxSize ) {
            maxSize = inc[v].size();
            h = v;
        }
    }

    inc[u][-1] = 0;
    if ( h == -1 ) {
        inc[u][0] -= cost[u];
        inc[u][height[u] + 1] += cost[u];

    } else {
        swap( inc[u], inc[h] );
        for ( int v: children[u] ) {
            if ( v == h )
                continue;
            for ( auto x: inc[v] )
                inc[u][x.first] += x.second;
            inc[v].clear();
        }

        auto p = inc[u].lower_bound( height[u] );
        if ( p != inc[u].begin() ) {
            p--;
            long long c = inc[u][height[u]];
            vector<pair<int, long long>> pos;
            pos.push_back( { height[u], 0 } );
            while ( p->first != -1 && c <= cost[u] ) {
                pos.push_back( { p->first, c } );
                c += p->second;
                p--;
            }
            inc[u][pos.back().first] += pos.back().second - cost[u];
            for ( int i = pos.size() - 2; i >= 0; i-- )
                inc[u].erase( pos[i].first );
            inc[u][height[u] + 1] += cost[u];
        }
    }
    inc[u][-1] = 0;
}

stack <int> st;
vector<vector<int>> cycles;
bool foundCycle;
bool onCycle[MAX_N + 1];
void findCycle( int u ) {
    vis[u] = true;
    st.push( u );
    for ( int v: edges[u] ) {
        if ( vis[v] ) {
            vector<int> c;
            c.push_back( v );
            onCycle[v] = true;
            while ( st.top() != v ) {
                c.push_back( st.top() );
                onCycle[st.top()] = true;
                st.pop();
            }
            cycles.push_back( c );
            return;
        }
        findCycle( v );
        if ( foundCycle )
            return;
    }
    st.pop();
}

map<int, int> mp;

int main() {
    long long c = 0;

    cin >> n;
    for ( int v = 1; v <= n; v++ ) {
        cin >> parent[v] >> height[v] >> cost[v];
        edges[parent[v]].push_back( v );
        c += cost[v];
    }

    for ( int v = 1; v <= n; v++ ) {
        if ( vis[v] )
            continue;
        findCycle( v );
    }
    /*for ( int i = 0; i < cycles.size(); i++ ) {
        for ( int v: cycles[i] )
            cout << v << " ";
        cout << "\n";
    }*/
    for ( int v = 1; v <= n; v++ ) {
        if ( !onCycle[v] )
            children[parent[v]].push_back( v );
    }
    for ( int v = 1; v <= n; v++ ) {
        if ( onCycle[v] ) {
            for ( int u: children[v] )
                computeDP( u );
        }
    }

    long long ans = c;
    for ( vector<int> cycle: cycles ) {
        map<int, long long> upd;
        for ( int v: cycle ) {
            upd[height[v]] -= cost[v];
            upd[height[v] + 1] += cost[v];
            for ( int u: children[v] ) {
                //cout << u << "\n";
                for ( auto p: inc[u] )
                    upd[p.first] += p.second;// printf( "l %d %d\n", p.first, p.second );
            }
        }
        long long minS = LONG_LONG_MAX, s = 0;
        for ( auto p: upd ) {
            //printf( "%d %d\n", p.first, p.second );
            s += p.second;
            if ( s < minS )
                minS = s;
        }
        ans += minS;
        //printf( "minS %d\n\n\n", minS );
    }

    cout << ans;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

worst_reporter2.cpp: In function 'void computeDP(int)':
worst_reporter2.cpp:21:28: warning: comparison of integer expressions of different signedness: 'std::map<int, long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         if ( inc[v].size() > maxSize ) {
      |              ~~~~~~~~~~~~~~^~~~~~~~~

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