Submission #899682

#	Time	Username	Problem	Language	Result	Execution time	Memory
899682		LucaIlie	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	447 ms	96932 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;
}

vector<int> st;
vector<vector<int>> cycles;
bool onCycle[MAX_N + 1];

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] || edges[v].size() > 0 )
            continue;
        vector<int> vert;
        int u = v;
        while ( !vis[u] ) {
            vert.push_back( u );
            vis[u] = true;
            u = parent[u];
        }
        int i = vert.size() - 1;
        vector<int> cycle;
        while ( i >= 0 && vert[i] != u ) {
            cycle.push_back( vert[i] );
            i--;
        }
        cycle.push_back( u );
        if ( i >= 0 )
            cycles.push_back( cycle );
    }
    for ( int v = 1; v <= n; v++ ) {
        if ( vis[v] )
            continue;
        vector<int> vert;
        int u = v;
        while ( !vis[u] ) {
            vert.push_back( u );
            vis[u] = true;
            u = parent[u];
        }
        int i = vert.size() - 1;
        vector<int> cycle;
        while ( i >= 0 && vert[i] != u ) {
            cycle.push_back( vert[i] );
            i--;
        }
        cycle.push_back( u );
        if ( i >= 0 )
            cycles.push_back( cycle );
    }
    for ( int i = 0; i < cycles.size(); i++ ) {
        for ( int v: cycles[i] )
            onCycle[v] = true;
    }
    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] ) {
                for ( auto p: inc[u] )
                    upd[p.first] += p.second;
            }
        }
        long long minS = LONG_LONG_MAX, s = 0;
        for ( auto p: upd ) {
            s += p.second;
            if ( s < minS )
                minS = s;
        }
        ans += minS;
    }

    cout << ans;

    return 0;
}

Compilation message (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 ) {
      |              ~~~~~~~~~~~~~~^~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:116:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for ( int i = 0; i < cycles.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~

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