Submission #821907

#	Time	Username	Problem	Language	Result	Execution time	Memory
821907		LucaIlie	Construction of Highway (JOI18_construction)	C++17	16 / 100	2079 ms	25352 KiB

construction

#include <bits/stdc++.h>

using namespace std;

const int UNDEF = 0;
const int MAX_N = 1e5;
int c[MAX_N], parent[MAX_N], ord[MAX_N];
vector<int> edges[MAX_N];

struct vr {
    int val, rep;
};

struct info {
    vector<vr> v;

    info operator + ( info &a ) {
        vector<vr> ans = v;
        for ( vr x: a.v ) {
            if ( !ans.empty() && ans.back().val == x.val )
                ans[ans.size() - 1].rep += x.rep;
            else
                ans.push_back( x );
        }

        return { ans };
    }
};


struct SegTree {

    info segTree[4 * MAX_N];
    int lazy[4 * MAX_N];

    void init() {
        for ( int v = 0; v < 4 * MAX_N; v++ )
            lazy[v] = UNDEF;
    }

    void propag( int v, int l, int r ) {
        if ( lazy[v] == UNDEF )
            return;

        segTree[v].v.clear();
        segTree[v].v.push_back( { lazy[v], r - l + 1 } );
        if ( l != r )
            lazy[v * 2 + 1] = lazy[v * 2 + 2] = lazy[v];
        lazy[v] = UNDEF;
    }

    void update( int v, int l, int r, int lu, int ru, int x ) {
        //if ( v == 0 )
            //printf( "%d %d %d\n", lu, ru, x );
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
    }

    info query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return {};

        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        info a = query( v * 2 + 1, l, mid, lq, rq );
        info b = query( v * 2 + 2, mid + 1, r, lq, rq );
        return a + b;
    }
};

struct HPD {
    int n, curPos;
    int sz[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[MAX_N], rightPos[MAX_N];
    SegTree aint;

    void dfs( int u, int p ) {
        int maxSz = -1;

        parent[u] = p;
        depth[u] = depth[p] + 1;
        sz[u] = 1;
        heavy[u] = UNDEF;
        for ( int v: edges[u] ) {
            if ( v == p )
                continue;
            dfs( v, u );
            sz[u] += sz[v];
            if ( sz[v] > maxSz ) {
                maxSz = sz[v];
                heavy[u] = v;
            }
        }
    }

    void decomp( int u, int p, int h ) {
        head[u] = h;
        leftPos[u] = ++curPos;
        if ( heavy[u] != UNDEF )
            decomp( heavy[u], u, h );
        for ( int v: edges[u] ) {
            if ( v == p || v == heavy[u] )
                continue;
            decomp( v, u, v );
        }
        rightPos[u] = curPos;
    }

    void init( int _n ) {
        n = _n;
        aint.init();
        parent[1] = UNDEF;
        dfs( 1, UNDEF );
        decomp( 1, UNDEF, 1 );
    }


    void updatePath( int u, int x ) {
        while ( u != 0 ) {
            aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
            u = parent[head[u]];
        }
    }

    info queryPath( int u ) {
        info ans;

        while ( u != 0 ) {
            info a = aint.query( 0, 1, n, leftPos[head[u]], leftPos[u] );
            ans = a + ans;
            u = parent[head[u]];
        }

        return ans;
    }
};

struct AIB {
    int aib[MAX_N + 1];

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int sum = 0;
        while ( i > 0 ) {
            sum += aib[i];
            i -= (i & -i);
        }
        return sum;
    }
};

AIB aib;
HPD arb;
map<int, int> normal;

int main() {
    int n;

    cin >> n;
    for ( int u = 1; u <= n; u++ )
        cin >> c[u], normal[c[u]] = 1;
    int val = 0;
    for ( auto x: normal )
        normal[x.first] = ++val;
    for ( int u = 1; u <= n; u++ )
        c[u] = normal[c[u]];

    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        parent[v] = u;
        edges[u].push_back( v );
        ord[i] = v;
    }

    arb.init( n );
    arb.updatePath( 1, c[1] );
    for ( int i = 0; i < n - 1; i++ ) {
        int u = ord[i];
        vector<vr> v = arb.queryPath( parent[u] ).v;

        int sum = 0;
        long long ans = 0;
        for ( vr x: v ) {
            ans += (long long)x.rep * (sum - aib.query( x.val ));
            aib.update( x.val, x.rep );
            sum += x.rep;
        }
        for ( vr x: v )
            aib.update( x.val, -x.rep );
        cout << ans << "\n";

        arb.updatePath( u, c[u] );
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84