oj.uz

Submission #642821

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

int n, q, tot[N], bad_ch[N], add_leaves[N], add_edges[N];
mii 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=-1, mxu=-1;
    for(auto x : ad[u]){
        if(x==pst) continue;
        if(sz(add[x])>mx){
            mx=sz(add[x]);
            mxu=x;
        }
    }

    swap(add[u], 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{
                add[a][i]++;
                add_leaves[i]++;
            }
            st.insert(a);
        }
        add_edges[i]=d;
    }


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

    int tot_leaf=0;
    FOR(i, 0, n)
    {
        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:133:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  133 |         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 4 ms 7380 KB Output is correct
2 Incorrect 81 ms 11220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9052 KB Output is correct
2 Correct 21 ms 9088 KB Output is correct
3 Correct 59 ms 26124 KB Output is correct
4 Correct 102 ms 30048 KB Output is correct
5 Correct 48 ms 24232 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 11496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 14028 KB Output is correct
2 Incorrect 104 ms 13396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 17364 KB Output is correct
2 Execution timed out 1087 ms 21104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 81 ms 11220 KB Output isn't correct
3 Halted 0 ms 0 KB -