oj.uz

Submission #643168

# Submission time Handle Problem Language Result Execution time Memory
643168 2022-09-21T11:24:17 Z idas Spring cleaning (CEOI20_cleaning) C++11
100 / 100
 173 ms 36712 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".txt").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=1e5+10;

//tot - total amount of leaves in a subtree
//add - number of added leaves to each query for each N node
//bad_ch - number of bad vertices changed during dfs

ll n, q, tot[N], bad_ch[N], add_leaves[N], add_edges[N], good_to[N], bad_to[N];
//map<int, int> add[N];
unordered_set<int> add[N];
vi ad[N];

void add_lf(int a, int i)
{
    if(add[a].count(i)){
        add[a].erase(i);
        bad_ch[i]-=2*good_to[a];
        bad_ch[i]+=2*bad_to[a];
    }
    else{
        add[a].insert(i);
    }
}

void calc_ch(int a, int i)
{
    bad_ch[i]+=good_to[a];
    bad_ch[i]-=bad_to[a];
}

void pre(int u, int pst)
{
    for(auto x : ad[u]){
        if(x==pst) continue;
        pre(x, u);
        tot[u]+=tot[x];
    }
    if(sz(ad[u])==1) tot[u]++;
}

void calc(int u, int pst, int tot_bad=0, int tot_good=0)
{
    if(tot[u]&1) tot_good++;
    else tot_bad++;
    good_to[u]=tot_good;
    bad_to[u]=tot_bad;
    for(auto x : ad[u]){
        if(x==pst) continue;
        calc(x, u, tot_bad, tot_good);
    }
}

void dfs(int u, int pst)
{
    for(auto x : ad[u]){
        if(x==pst) continue;
        dfs(x, u);
    }

    int mx=sz(add[u]), mxu=u;
    for(auto x : ad[u]){
        if(x==pst) continue;
        if(sz(add[x])>mx){
            mx=sz(add[x]);
            mxu=x;
        }
    }

    if(mxu!=u) add[u].swap(add[mxu]);

    for(auto x : ad[u]){
        if(x==pst) continue;
        for(auto it : add[x]){
            add_lf(u, it);
        }
//        add[x].clear();
    }
}

int main()
{
    setIO();
    cin >> n >> q;
    FOR(i, 0, n-1)
    {
        int a, b; cin >> a >> b; a--; b--;
        ad[a].pb(b);
        ad[b].pb(a);
    }

    pre(0, -1);
    calc(0, -1);

    FOR(i, 0, q)
    {
        set<int> st;
        int d; cin >> d;
        FOR(j, 0, d)
        {
            int a; cin >> a; --a;
            if(sz(ad[a])==1){
                if(st.count(a)){
                    add_lf(a, i);

                    calc_ch(a, i);

                    add_leaves[i]++;
                }
                else{
                    st.insert(a);
                }
            }
            else{
                add_lf(a, i);

                calc_ch(a, i);

                add_leaves[i]++;
            }
        }
        add_edges[i]=d;
    }


    int tot_bad=-1, tot_leaf=0; //(we exclude root as it has no parent vertex)
    FOR(i, 0, n)
    {
        if(tot[i]&1^1){
            ++tot_bad;
        }
        if(sz(ad[i])==1){
            ++tot_leaf;
        }
    }

    dfs(0, -1);

    int pre_ans=n-1+tot_bad;
    FOR(i, 0, q)
    {
        if((tot_leaf+add_leaves[i])&1){
            cout << "-1\n";
            continue;
        }

        cout << pre_ans+add_edges[i]+bad_ch[i] << '\n';
    }
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:164:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  164 |         if(tot[i]&1^1){
      |            ~~~~~~^~
cleaning.cpp: In function 'void setIO(std::string)':
cleaning.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen((s+".txt").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 58 ms 15564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9236 KB Output is correct
2 Correct 23 ms 9216 KB Output is correct
3 Correct 42 ms 15008 KB Output is correct
4 Correct 88 ms 19008 KB Output is correct
5 Correct 91 ms 21160 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9832 KB Output is correct
2 Correct 18 ms 9828 KB Output is correct
3 Correct 61 ms 22736 KB Output is correct
4 Correct 95 ms 29140 KB Output is correct
5 Correct 49 ms 21136 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12624 KB Output is correct
2 Correct 31 ms 11616 KB Output is correct
3 Correct 13 ms 9496 KB Output is correct
4 Correct 15 ms 10016 KB Output is correct
5 Correct 15 ms 10324 KB Output is correct
6 Correct 35 ms 13164 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 28072 KB Output is correct
2 Correct 88 ms 22204 KB Output is correct
3 Correct 83 ms 18412 KB Output is correct
4 Correct 106 ms 22784 KB Output is correct
5 Correct 91 ms 22388 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 33784 KB Output is correct
2 Correct 136 ms 30212 KB Output is correct
3 Correct 173 ms 36644 KB Output is correct
4 Correct 137 ms 36712 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 58 ms 15564 KB Output is correct
3 Correct 25 ms 9236 KB Output is correct
4 Correct 23 ms 9216 KB Output is correct
5 Correct 42 ms 15008 KB Output is correct
6 Correct 88 ms 19008 KB Output is correct
7 Correct 91 ms 21160 KB Output is correct
8 Correct 18 ms 9832 KB Output is correct
9 Correct 18 ms 9828 KB Output is correct
10 Correct 61 ms 22736 KB Output is correct
11 Correct 95 ms 29140 KB Output is correct
12 Correct 49 ms 21136 KB Output is correct
13 Correct 37 ms 12624 KB Output is correct
14 Correct 31 ms 11616 KB Output is correct
15 Correct 13 ms 9496 KB Output is correct
16 Correct 15 ms 10016 KB Output is correct
17 Correct 15 ms 10324 KB Output is correct
18 Correct 35 ms 13164 KB Output is correct
19 Correct 111 ms 28072 KB Output is correct
20 Correct 88 ms 22204 KB Output is correct
21 Correct 83 ms 18412 KB Output is correct
22 Correct 106 ms 22784 KB Output is correct
23 Correct 91 ms 22388 KB Output is correct
24 Correct 141 ms 33784 KB Output is correct
25 Correct 136 ms 30212 KB Output is correct
26 Correct 173 ms 36644 KB Output is correct
27 Correct 137 ms 36712 KB Output is correct
28 Correct 85 ms 20000 KB Output is correct
29 Correct 106 ms 21212 KB Output is correct
30 Correct 86 ms 21108 KB Output is correct
31 Correct 88 ms 29136 KB Output is correct
32 Correct 96 ms 21984 KB Output is correct
33 Correct 111 ms 24420 KB Output is correct
34 Correct 147 ms 27048 KB Output is correct
35 Correct 148 ms 26804 KB Output is correct