oj.uz

Submission #660715

# Submission time Handle Problem Language Result Execution time Memory
660715 2022-11-22T20:57:05 Z Lobo Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 503 ms 19460 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;

int n, q, gr[maxn], p[maxn], sbl[maxn];
vector<int> g[maxn];
int cntl;
int tr[4*maxn], lz[4*maxn], tin[maxn], tout[maxn], timer;
int sbsz[maxn], phld[maxn];

void build(int no, int l, int r) {
    lz[no] = 0;
    if(l == r) {
        tr[no] = 0;
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[no] = tr[lc]+tr[rc];
}

void flush(int no, int l, int r) {
    if(!lz[no]) return;

    tr[no] = (r-l+1)-tr[no];
    if(l != r) {
        int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
        lz[lc]^= 1;
        lz[rc]^= 1;
    }
    lz[no] = 0;
}
void upd(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lz[no] = 1;
        flush(no,l,r);
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    upd(lc,l,mid,L,R);
    upd(rc,mid+1,r,L,R);
    tr[no] = tr[lc]+tr[rc];
}

int qry(int no, int l, int r, int L, int R) {
    flush(no,l,r);
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) {
        return tr[no];
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return qry(lc,l,mid,L,R)+qry(rc,mid+1,r,L,R);
}

void dfs(int u, int ant) {
    p[u] = ant;
    // tin[u] = ++timer;
    if(gr[u] == 1) {
        cntl++;
        sbl[u] = 1;
    }
    else sbl[u] = 0;
    sbsz[u] = 1;
    for(auto v : g[u]) if(v != ant) {
        dfs(v,u);
        sbl[u]^= sbl[v];
        sbsz[u]+= sbsz[v];
    }
    // tout[u] = timer;
}

void dfshld(int u, int ant) {
    tin[u] = ++timer;
    if(gr[u] == 1) {
        tout[u] = timer;
        return;
    }
    if(g[u][0] == ant) {
        swap(g[u][0],g[u][1]);
    }

    for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
        if(sbsz[g[u][i]] > sbsz[g[u][0]]) swap(g[u][i],g[u][0]);
    }

    phld[g[u][0]] = phld[u];
    dfshld(g[u][0],u);
    for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
        int v = g[u][i];
        phld[v] = v;
        dfshld(v,u);
    }
    tout[u] = timer;
}

void change(int v) {
    // while(v != -1) {
    //     upd(1,1,n,tin[v],tin[v]);
    //     v = p[v];
    // }

    while(v != -1) {
        int nx = phld[v];
        upd(1,1,n,tin[nx],tin[v]);
        v = p[nx];
    }
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        gr[u]++;
        gr[v]++;
    }

    int rt;
    for(int i = 1; i <= n; i++) {
        if(gr[i] != 1) {
            rt = i;
            break;
        }
    }
    dfs(rt,-1);
    phld[rt] = rt;
    dfshld(rt,-1);

    build(1,1,n);
    for(int i = 1; i <= n; i++) {
        if(sbl[i] == 1) upd(1,1,n,tin[i],tin[i]);
    }

    while(q--) {
        int D; cin >> D;
        vector<int> as;
        for(int i = 0; i < D; i++) {
            int v; cin >> v;
            as.pb(v);

            if(gr[v] == 1) {
                cntl--;
                change(v);
            }
            gr[v]++;
            cntl++;
            change(v);
        }

        if(cntl%2 == 1) {
            cout << -1 << endl;
        }
        else {
            int q1 = tr[1]+D;
            int q2 = n-1-tr[1];
            cout << q1 + 2*q2 << endl;
        }

        for(int i = 0; i < D; i++) {
            int v = as[i];
            gr[v]--;
            if(gr[v] == 1) {
                cntl++;
                change(v);
            }
            cntl--;
            change(v);
        }

    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

cleaning.cpp: In function 'void flush(int, int, int)':
cleaning.cpp:39:31: warning: unused variable 'mid' [-Wunused-variable]
   39 |         int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
      |                               ^~~
cleaning.cpp: In function 'void dfshld(int, int)':
cleaning.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
      |                    ~~^~~~~~~~~~~~~
cleaning.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 1; i < g[u].size(); i++) if(g[u][i] != ant) {
      |                    ~~^~~~~~~~~~~~~
cleaning.cpp: In function 'void solve()':
cleaning.cpp:142:11: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |     dfshld(rt,-1);
      |     ~~~~~~^~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 230 ms 4564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3540 KB Output is correct
2 Correct 50 ms 3604 KB Output is correct
3 Correct 70 ms 11008 KB Output is correct
4 Correct 144 ms 9808 KB Output is correct
5 Correct 168 ms 11752 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4112 KB Output is correct
2 Correct 44 ms 4496 KB Output is correct
3 Correct 74 ms 19460 KB Output is correct
4 Correct 124 ms 19156 KB Output is correct
5 Correct 57 ms 17980 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 5336 KB Output is correct
2 Correct 83 ms 4788 KB Output is correct
3 Correct 14 ms 4564 KB Output is correct
4 Correct 12 ms 5096 KB Output is correct
5 Correct 16 ms 5340 KB Output is correct
6 Correct 79 ms 5276 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 7844 KB Output is correct
2 Correct 503 ms 7656 KB Output is correct
3 Correct 412 ms 5184 KB Output is correct
4 Correct 489 ms 7756 KB Output is correct
5 Correct 492 ms 7756 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 11080 KB Output is correct
2 Correct 204 ms 14392 KB Output is correct
3 Correct 203 ms 15872 KB Output is correct
4 Correct 209 ms 15212 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 230 ms 4564 KB Output is correct
3 Correct 51 ms 3540 KB Output is correct
4 Correct 50 ms 3604 KB Output is correct
5 Correct 70 ms 11008 KB Output is correct
6 Correct 144 ms 9808 KB Output is correct
7 Correct 168 ms 11752 KB Output is correct
8 Correct 44 ms 4112 KB Output is correct
9 Correct 44 ms 4496 KB Output is correct
10 Correct 74 ms 19460 KB Output is correct
11 Correct 124 ms 19156 KB Output is correct
12 Correct 57 ms 17980 KB Output is correct
13 Correct 108 ms 5336 KB Output is correct
14 Correct 83 ms 4788 KB Output is correct
15 Correct 14 ms 4564 KB Output is correct
16 Correct 12 ms 5096 KB Output is correct
17 Correct 16 ms 5340 KB Output is correct
18 Correct 79 ms 5276 KB Output is correct
19 Correct 318 ms 7844 KB Output is correct
20 Correct 503 ms 7656 KB Output is correct
21 Correct 412 ms 5184 KB Output is correct
22 Correct 489 ms 7756 KB Output is correct
23 Correct 492 ms 7756 KB Output is correct
24 Correct 384 ms 11080 KB Output is correct
25 Correct 204 ms 14392 KB Output is correct
26 Correct 203 ms 15872 KB Output is correct
27 Correct 209 ms 15212 KB Output is correct
28 Correct 337 ms 8852 KB Output is correct
29 Correct 193 ms 15620 KB Output is correct
30 Correct 175 ms 12948 KB Output is correct
31 Correct 130 ms 19272 KB Output is correct
32 Correct 478 ms 8864 KB Output is correct
33 Correct 200 ms 13464 KB Output is correct
34 Correct 219 ms 15576 KB Output is correct
35 Correct 222 ms 15436 KB Output is correct