제출 #762464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762464		LucaIlie	Min-max tree (BOI18_minmaxtree)	C++17	36 / 100	137 ms	38264 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 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];
}

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 MULT = (1 << 30);
    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 ) {
        //printf( "edge %d %d\n", u, v );
        edges[u].push_back( v );
    }

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

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

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

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

        return dist[NIL] != MULT;
    }

    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] = MULT;

        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 );
            }
        }

        /*printf( "aici\n" );
        for ( int u = 1; u <= n; u++ )
            printf( "%d %d\n", u, pairU[u] );
        printf( "\n" );*/
    }
};

MATCH match;

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 } );
    }

    sort( mins.begin(), mins.end() );
    reverse( mins.begin(), mins.end() );
    for ( int u = 1; u <= n; u++ ) {
        asc[u] = parent[0][u];
        queryMin[u] = undef;
        used[u] = false;
    }
    for ( int i = 0; i < mins.size(); i++ ) {
        int u = mins[i].u, v = mins[i].v;
        int l = lca( u, v );
        while ( depth[u] > depth[l] ) {
            if ( !used[u] ) {
                used[u] = true;
                queryMin[u] = i;
            }
            u = parent[0][u];
        }
        while ( depth[v] > depth[l] ) {
            if ( !used[v] ) {
                used[v] = true;
                queryMin[v] = i;
            }
            v = parent[0][v];
        }
    }

    sort( maxs.begin(), maxs.end() );
    for ( int u = 1; u <= n; u++ ) {
        asc[u] = parent[0][u];
        queryMax[u] = undef;
        used[u] = false;
    }
    for ( int i = 0; i < maxs.size(); i++ ) {
        int u = maxs[i].u, v = maxs[i].v;
        int l = lca( u, v );

        while ( depth[u] > depth[l] ) {
            if ( !used[u] ) {
                used[u] = true;
                queryMax[u] = i;
            }
            u = parent[0][u];
        }
        while ( depth[v] > depth[l] ) {
            if ( !used[v] ) {
                used[v] = true;
                queryMax[v] = i;
            }
            v = parent[0][v];
        }
    }

    //for ( int u = 2; u <= n; u++ )
        //printf( "%d %d\n", queryMin[u], queryMax[u] );

    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 )
            value[u] = max( mins[queryMin[u]].w, maxs[queryMax[u]].w );
        if ( value[u] == undef )
            value[u] = 0;
        cout << u << " " << parent[0][u] << " " << value[u] << "\n";
    }

    return 0;
}

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

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

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