Submission #823307

#	Time	Username	Problem	Language	Result	Execution time	Memory
823307		LucaIlie	Construction of Highway (JOI18_construction)	C++17	7 / 100	1722 ms	9644 KiB

construction

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

struct vr {
    int val, rep;
};

const int UNDEF = 0;
const int INF = 1e9;
const int MAX_N = 1e5;
const int MAX_LOG_N = 17;
int c[MAX_N], parent[MAX_LOG_N + 1][MAX_N], ord[MAX_N];
vector<int> edges[MAX_N];
vr elem[MAX_N];

struct info {
    int minn, maxx;

    info operator + ( info &x ) const {
        return { min( minn, x.minn ), max( maxx, x.maxx ) };
    }
};

struct SegTree {
    info segTree[4 * MAX_N];
    int lazy[4 * MAX_N];

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

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

        segTree[v] = { lazy[v], lazy[v] };
        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 ) {
        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 { INF, -INF };

        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[0][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[0][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[0][head[u]];
        }
    }

    info queryPath( int u, int v ) {
       info ans = { INF, -INF };

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

        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() {
    ios_base::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );
    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[0][v] = u;
        edges[u].push_back( v );
        ord[i] = v;
    }

    for ( int pas = 1; pas <= MAX_LOG_N; pas++ ) {
        for ( int u = 1; u <= n; u++ )
            parent[pas][u] = parent[pas - 1][parent[pas - 1][u]];
    }

    arb.init( n );
    arb.updatePath( 1, c[1] );
    int sumSize = 0;
    for ( int i = 0; i < n - 1; i++ ) {
        int u = ord[i];
        int elemSize = 0;

        int v = parent[0][u];
        while( v != UNDEF ) {
            int c = arb.queryPath( v, v ).minn;
            int nr = 1;
            for ( int pas = MAX_LOG_N; pas >= 0; pas-- ) {
                if ( parent[pas][v] != UNDEF && arb.queryPath( u, parent[pas][v] ).maxx == c && arb.queryPath( u, parent[pas][v] ).minn == c ) {
                    v = parent[pas][v];
                    nr += (1 << pas);
                }
            }
            elem[elemSize++] = { c, nr };
            v = parent[0][v];
        }
        sumSize += elemSize;

        long long ans = 0;
        for ( int i = 0; i < elemSize; i++ ) {
            vr x = elem[i];
            ans += (long long)x.rep * aib.query( x.val -1 );
            aib.update( x.val, x.rep );
        }
        for ( int i = 0; i < elemSize; i++ ) {
            vr x = elem[i];
            aib.update( x.val, -x.rep );
        }
        cout << ans << "\n";

        arb.updatePath( u, c[u] );
        if ( sumSize > 1e6 )
            return 1;
    }

    return 0;
}

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