oj.uz

Submission #642838

# Submission time Handle Problem Language Result Execution time Memory
642838 2022-09-20T15:36:13 Z idas Spring cleaning (CEOI20_cleaning) C++11
53 / 100
 1000 ms 29136 KB 
#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;

//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

int n, q, tot[N], bad_ch[N], add_leaves[N], add_edges[N];
unordered_map<int, int> add[N];
vi ad[N];

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 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[u][it.f]+=it.s;
        }
//        add[x].clear();
    }

    for(auto it : add[u]){
        if(it.s&1){
            if(tot[u]&1){
                bad_ch[it.f]++;
            }
            else{
                bad_ch[it.f]--;
            }
        }
    }
}

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

    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[a][i]++;
                    add_leaves[i]++;
                }
                else{
                    st.insert(a);
                }
            }
            else{
                add[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);

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

        cout << n-1+add_edges[i]+tot_bad+bad_ch[i] << '\n';
    }
}

Compilation message

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 54 ms 14924 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8788 KB Output is correct
2 Correct 20 ms 8820 KB Output is correct
3 Correct 33 ms 12236 KB Output is correct
4 Correct 76 ms 16872 KB Output is correct
5 Correct 96 ms 17960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9560 KB Output is correct
2 Correct 18 ms 9560 KB Output is correct
3 Correct 54 ms 22728 KB Output is correct
4 Correct 83 ms 29136 KB Output is correct
5 Correct 46 ms 21192 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11864 KB Output is correct
2 Correct 24 ms 10916 KB Output is correct
3 Correct 12 ms 8928 KB Output is correct
4 Correct 19 ms 9684 KB Output is correct
5 Correct 26 ms 10032 KB Output is correct
6 Correct 48 ms 12484 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 25000 KB Output is correct
2 Correct 86 ms 20932 KB Output is correct
3 Correct 60 ms 18124 KB Output is correct
4 Correct 123 ms 21688 KB Output is correct
5 Correct 102 ms 21232 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 28784 KB Output is correct
2 Execution timed out 1083 ms 24476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 54 ms 14924 KB Output is correct
3 Correct 22 ms 8788 KB Output is correct
4 Correct 20 ms 8820 KB Output is correct
5 Correct 33 ms 12236 KB Output is correct
6 Correct 76 ms 16872 KB Output is correct
7 Correct 96 ms 17960 KB Output is correct
8 Correct 21 ms 9560 KB Output is correct
9 Correct 18 ms 9560 KB Output is correct
10 Correct 54 ms 22728 KB Output is correct
11 Correct 83 ms 29136 KB Output is correct
12 Correct 46 ms 21192 KB Output is correct
13 Correct 56 ms 11864 KB Output is correct
14 Correct 24 ms 10916 KB Output is correct
15 Correct 12 ms 8928 KB Output is correct
16 Correct 19 ms 9684 KB Output is correct
17 Correct 26 ms 10032 KB Output is correct
18 Correct 48 ms 12484 KB Output is correct
19 Correct 87 ms 25000 KB Output is correct
20 Correct 86 ms 20932 KB Output is correct
21 Correct 60 ms 18124 KB Output is correct
22 Correct 123 ms 21688 KB Output is correct
23 Correct 102 ms 21232 KB Output is correct
24 Correct 135 ms 28784 KB Output is correct
25 Execution timed out 1083 ms 24476 KB Time limit exceeded
26 Halted 0 ms 0 KB -