Submission #762543

#	Time	Username	Problem	Language	Result	Execution time	Memory
762543		LucaIlie	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	334 ms	46400 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

struct query {
    int u, v, w;

    bool operator < ( const query &q ) const {
        return w < q.w;
    }
};

const int INF = (1 << 30);
const int MAX_N = 7e4 + 1;
const int MAX_LOG_N = 16;
const int undef = -1;
bool used[MAX_N];
int depth[MAX_N], parent[MAX_LOG_N + 1][MAX_N], asc[MAX_N], queryMin[MAX_N], queryMax[MAX_N], value[MAX_N];
vector<int> edges[MAX_N];
vector<query> mins, maxs;

void dfs( int u, int p ) {
    depth[u] = depth[p] + 1;
    parent[0][u] = p;
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

int lca( int u, int v ) {
    if ( depth[u] > depth[v] )
        swap( u, v );
    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( depth[parent[p][v]] >= depth[u] )
            v = parent[p][v];
    }
    if ( u == v )
        return u;
    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( parent[p][u] != parent[p][v] ) {
            u = parent[p][u];
            v = parent[p][v];
        }
    }
    return parent[0][v];
}

int findParent( int u, int d ) {
    if ( d < 0 )
        return undef;

    for ( int p = MAX_LOG_N; p >= 0; p-- ) {
        if ( d >= (1 << p) ) {
            u = parent[p][u];
            d -= (1 << p);
        }
    }
    return u;
}

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

struct MATCH {
    const int NIL = 0;

    int n, m;
    int pairU[MAX_N + 1], pairV[MAX_N + 1], dist[MAX_N + 1];
    vector <int> edges[MAX_N + 1];

    void init( int _n, int _m ) {
        n = _n;
        m = _m;
    }

    void add_edge( int u, int v ) {
        edges[u].push_back( v );
    }

    bool bfs() {
        int u;
        queue <int> q;

        dist[NIL] = INF;
        for ( u = 1; u <= n; u++ ) {
            if ( pairU[u] == NIL ) {
                dist[u] = 0;
                q.push( u );
            } else
                dist[u] = INF;
        }

        while ( !q.empty() ) {
            u = q.front();
            q.pop();

            if ( dist[u] < dist[NIL] ) {
                for ( int v: edges[u] ) {
                    if ( dist[pairV[v]] == INF ) {
                        dist[pairV[v]] = dist[u] + 1;
                        q.push( pairV[v] );
                    }
                }
            }
        }

        return dist[NIL] != INF;
    }

    bool dfs( int u ) {
        if ( u == NIL )
            return true;

        for ( int v: edges[u] ) {
            if ( dist[pairV[v]] == dist[u] + 1 && dfs( pairV[v] ) ) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }

        dist[u] = INF;

        return false;
    }

    void maxMatch() {
        int maxMatch, u, v;

        for ( u = 0; u <= n; u++ )
            pairU[u] = NIL;
        for ( v = 0; v <= m; v++ )
            pairV[v] = NIL;


        while ( bfs() ) {
            for ( u = 1; u <= n; u++ ) {
                if ( pairU[u] == NIL )
                    dfs( u );
            }
        }
    }
};

MATCH match;


struct info {
    int minn, maxx;

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

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

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

    void propag( int v, int l, int r ) {
        segTree[v] = segTree[v] + lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
            lazy[v * 2 + 2] = lazy[v * 2 + 2] + lazy[v];
        }
    }

    void update( int v, int l, int r, int lu, int ru, info 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;
        return query( v * 2 + 1, l, mid, lq, rq ) + query( v * 2 + 2, mid + 1, r, lq, rq );
    }
};

struct HPD {
    int n, curPos;
    int sz[MAX_N], parent[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], leftPos[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 );
        }
    }

    void init( int _n ) {
        n = _n;
        aint.init();
        dfs( 1, 0 );
        decomp( 1, 0, 1 );
    }

    void updatePath( int u, int v, info x ) {
        while ( head[u] != head[v] ) {
            if ( depth[head[u]] < depth[head[v]] )
                swap( u, v );
            aint.update( 0, 1, n, leftPos[head[u]], leftPos[u], x );
            u = parent[head[u]];
        }
        if ( depth[u] > depth[v] )
            swap( u, v );
        aint.update( 0, 1, n, leftPos[u], leftPos[v], x );
    }

    info queryVertex( int u ) {
        return aint.query( 0, 1, n, leftPos[u], leftPos[u] );
    }
};

HPD arb;
unordered_map<int, int> indx;

int main() {
    int n, k;

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

    dfs( 1, 0 );
    init( n );

    cin >> k;
    for ( int i = 0; i < k; i++ ) {
        char ch;
        int u, v, w;
        cin >> ch >> u >> v >> w;
        if ( ch == 'm' )
            mins.push_back( { u, v, w } );
        else
            maxs.push_back( { u, v, w } );
    }

    arb.init( n );
    for ( int i = 0; i < mins.size(); i++ ) {
        indx[mins[i].w] = i;
        int u = mins[i].u, v = mins[i].v;
        int l = lca( u, v );
        int a = findParent( u, depth[u] - depth[l] - 1 );
        int b = findParent( v, depth[v] - depth[l] - 1 );
        if ( a != undef )
            arb.updatePath( u, a, { INF, mins[i].w, } );
        if ( b != undef )
            arb.updatePath( v, b, { INF, mins[i].w } );
    }
    for ( int i = 0; i < maxs.size(); i++ ) {
        indx[maxs[i].w] = i;
        int u = maxs[i].u, v = maxs[i].v;
        int l = lca( u, v );
        int a = findParent( u, depth[u] - depth[l] - 1 );
        int b = findParent( v, depth[v] - depth[l] - 1 );
        if ( a != undef )
            arb.updatePath( u, a, { maxs[i].w, -INF } );
        if ( b != undef )
            arb.updatePath( v, b, { maxs[i].w, -INF } );
    }
    indx[INF] = indx[-INF] = -1;

    for ( int u = 2; u <= n; u++ ) {
        queryMin[u] = indx[arb.queryVertex( u ).maxx];
        queryMax[u] = indx[arb.queryVertex( u ).minn];
        //printf( "%d %d\n", arb.queryVertex( u ).maxx, arb.queryVertex( u ).minn );
    }

    match.init( k, n - 1 );
    for ( int u = 2; u <= n; u++ ) {
        if ( queryMin[u] != -1 )
            match.add_edge( queryMin[u] + 1, u - 1 );
        if ( queryMax[u] != -1 )
            match.add_edge( mins.size() + queryMax[u] + 1, u - 1 );
    }
    match.maxMatch();

    for ( int u = 2; u <= n; u++ )
        value[u] = undef;
    for ( int i = 0; i < mins.size(); i++ )
        value[match.pairU[i + 1] + 1] = mins[i].w;
    for ( int i = 0; i < maxs.size(); i++ )
        value[match.pairU[mins.size() + i + 1] + 1] = maxs[i].w;

    for ( int u = 2; u <= n; u++ ) {
        if ( value[u] == undef ) {
            if ( queryMin[u] != undef )
                value[u] = mins[queryMin[u]].w;
            else if ( queryMax[u] != undef )
                value[u] = maxs[queryMax[u]].w;
            else
                value[u] = 0;
        }
        cout << u << " " << parent[0][u] << " " << value[u] << "\n";
    }

    return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In member function 'void MATCH::maxMatch()':
minmaxtree.cpp:134:13: warning: unused variable 'maxMatch' [-Wunused-variable]
  134 |         int maxMatch, u, v;
      |             ^~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:301:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  301 |     for ( int i = 0; i < mins.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~
minmaxtree.cpp:312:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  312 |     for ( int i = 0; i < maxs.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~
minmaxtree.cpp:342:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  342 |     for ( int i = 0; i < mins.size(); i++ )
      |                      ~~^~~~~~~~~~~~~
minmaxtree.cpp:344:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  344 |     for ( int i = 0; i < maxs.size(); i++ )
      |                      ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42