oj.uz

Submission #930837

# Submission time Handle Problem Language Result Execution time Memory
930837 2024-02-20T13:30:23 Z LucaIlie Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 398 ms 45720 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 171 ms 8024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 7248 KB Output is correct
2 Correct 82 ms 7260 KB Output is correct
3 Correct 82 ms 13672 KB Output is correct
4 Correct 106 ms 12012 KB Output is correct
5 Correct 122 ms 13876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9040 KB Output is correct
2 Correct 95 ms 9112 KB Output is correct
3 Correct 123 ms 45720 KB Output is correct
4 Correct 240 ms 42524 KB Output is correct
5 Correct 91 ms 42308 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 11100 KB Output is correct
2 Correct 58 ms 8540 KB Output is correct
3 Correct 16 ms 8280 KB Output is correct
4 Correct 19 ms 10588 KB Output is correct
5 Correct 20 ms 11356 KB Output is correct
6 Correct 89 ms 10488 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 11344 KB Output is correct
2 Correct 290 ms 11240 KB Output is correct
3 Correct 243 ms 9284 KB Output is correct
4 Correct 335 ms 11092 KB Output is correct
5 Correct 328 ms 11484 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 13904 KB Output is correct
2 Correct 324 ms 27476 KB Output is correct
3 Correct 382 ms 24360 KB Output is correct
4 Correct 370 ms 29852 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 171 ms 8024 KB Output is correct
3 Correct 79 ms 7248 KB Output is correct
4 Correct 82 ms 7260 KB Output is correct
5 Correct 82 ms 13672 KB Output is correct
6 Correct 106 ms 12012 KB Output is correct
7 Correct 122 ms 13876 KB Output is correct
8 Correct 88 ms 9040 KB Output is correct
9 Correct 95 ms 9112 KB Output is correct
10 Correct 123 ms 45720 KB Output is correct
11 Correct 240 ms 42524 KB Output is correct
12 Correct 91 ms 42308 KB Output is correct
13 Correct 104 ms 11100 KB Output is correct
14 Correct 58 ms 8540 KB Output is correct
15 Correct 16 ms 8280 KB Output is correct
16 Correct 19 ms 10588 KB Output is correct
17 Correct 20 ms 11356 KB Output is correct
18 Correct 89 ms 10488 KB Output is correct
19 Correct 267 ms 11344 KB Output is correct
20 Correct 290 ms 11240 KB Output is correct
21 Correct 243 ms 9284 KB Output is correct
22 Correct 335 ms 11092 KB Output is correct
23 Correct 328 ms 11484 KB Output is correct
24 Correct 398 ms 13904 KB Output is correct
25 Correct 324 ms 27476 KB Output is correct
26 Correct 382 ms 24360 KB Output is correct
27 Correct 370 ms 29852 KB Output is correct
28 Correct 231 ms 12208 KB Output is correct
29 Correct 246 ms 26056 KB Output is correct
30 Correct 116 ms 15304 KB Output is correct
31 Correct 232 ms 44152 KB Output is correct
32 Correct 291 ms 12812 KB Output is correct
33 Correct 219 ms 24024 KB Output is correct
34 Correct 274 ms 28568 KB Output is correct
35 Correct 231 ms 28016 KB Output is correct