Submission #930837

#	Time	Username	Problem	Language	Result	Execution time	Memory
930837		LucaIlie	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	398 ms	45720 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int undef = 0;
int leafs[MAX_N + 1], parent[MAX_N + 1], children[MAX_N + 1], a[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int ans;


void dfs( int u, int p ) {
    parent[u] = p;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        children[u]++;
        dfs( v, u );
        leafs[u] += leafs[v];
    }
    leafs[u] += (children[u] == 0);
    ans += 2 - leafs[u] % 2;
}

struct info {
    int nr0, nr1;

    info operator + ( info x ) {
        return { nr0 + x.nr0, nr1 + x.nr1 };
    }
};

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

    void init( int v, int l, int r ) {
        lazy[v] = 0;
        if ( l == r ) {
            segTree[v] = { 1, 0 };
            return;
        }
        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
        segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
    }

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

        swap( segTree[v].nr0, segTree[v].nr1 );
        if ( l != r ) {
            lazy[v * 2 + 1] ^= 1;
            lazy[v * 2 + 2] ^= 1;
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru ) {
        propag( v, l, r );

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

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

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru );
        update( v * 2 + 2, mid + 1, r, lu, ru );
        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 { 0, 0 };

        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, r, curPos;
    int sz[MAX_N], parent[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: adj[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: adj[u] ) {
            if ( v == p || v == heavy[u] )
                continue;
            decomp( v, u, v );
        }
        rightPos[u] = curPos;
    }

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

    void updatePath( int u, int v ) {
        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] );
            u = parent[head[u]];
        }
        if ( depth[u] > depth[v] )
            swap( u, v );
        aint.update( 0, 1, n, leftPos[u], leftPos[v] );
    }

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

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

        return ans;
    }
} arb;

int main() {
    int n, q;

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

    int r = 1;
    while ( adj[r].size() == 1 )
        r++;
    ans = 0;
    dfs( r, 0 );

    arb.init( n, r );
    for ( int v = 1; v <= n; v++ ) {
        if ( leafs[v] % 2 == 1 )
            arb.updatePath( v, v );
    }
    for ( int i = 0; i < q; i++ ) {
        int d;
        int change = 0;

        cin >> d;
        for ( int i = 0; i < d; i++ ) {
            cin >> a[i];
            int v = a[i];

            change++;
            children[v]++;
            if ( children[v] == 1 )
                continue;

            info x;

            x = arb.queryPath( v, r );
            change -= x.nr0 * 2 + x.nr1;

            arb.updatePath( v, r );

            x = arb.queryPath( v, r );
            change += x.nr0 * 2 + x.nr1;
        }

        info x = arb.queryPath( r, r );
        change -= x.nr0 * 2 + x.nr1;
        cout << (arb.queryPath( r, r ).nr0 == 1 ? ans + change : -1) << "\n";

        for ( int i = 0; i < d; i++ ) {
            int v = a[i];
            children[v]--;
            if ( children[v] == 0 )
                continue;
            arb.updatePath( v, r );
        }
    }


    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30