oj.uz

Submission #1002394

# Submission time Handle Problem Language Result Execution time Memory
1002394 2024-06-19T14:08:44 Z yoav_s Spring cleaning (CEOI20_cleaning) C++17
53 / 100
 1000 ms 229532 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

typedef int ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

ll getLeafCount(ll i, vv &graph, v &res)
{
    if (res[i] != -1) return 0;
    res[i] = 0;
    if (graph[i].size() == 1)
    {
        res[i] = 1;
        return 1;
    }
    for (ll x : graph[i]) res[i] += getLeafCount(x, graph, res);
    return res[i];
}

void getOddAndEvenParents(ll i, vv &graph, v &oddRes, v &evenRes, ll oddParents, ll evenParents, v &parity)
{
    if (oddRes[i] != -1) return;
    if (parity[i] % 2 == 0) evenParents++;
    else oddParents++;
    oddRes[i] = oddParents;
    evenRes[i] = evenParents;
    for (ll x : graph[i]) getOddAndEvenParents(x, graph, oddRes, evenRes, oddParents, evenParents, parity);
}

set<ll> *solve(ll i, vv &graph, vb &visited, v &res, vv &changes, v &oddParents, v &evenParents)
{
    visited[i] = true;
    vector<set<ll>*> childrenSets;
    for (ll x : graph[i])
    {
        if (visited[x]) continue;
        childrenSets.pb(solve(x, graph, visited, res, changes, oddParents, evenParents));
    }
    childrenSets.pb(new set<ll>());
    for (ll x : changes[i])
    {
        (*childrenSets.back()).insert(x);
        res[x] += oddParents[i] - evenParents[i];
    }
    set<ll> *baseSet = new set<ll>();
    ll maxiSize = -1;
    ll index = -1;
    for (ll i = 0; i < childrenSets.size(); i++)
    {
        if ((*childrenSets[i]).size() > maxiSize)
        {
            baseSet = childrenSets[i];
            maxiSize = (*childrenSets[i]).size();
            index = i;
        }
    }
    set<ll> newAdditions;
    for (ll j = 0; j < childrenSets.size(); j++)
    {
        if (j == index) continue;
        for (auto y : (*childrenSets[j]))
        {
            if ((*baseSet).count(y) > 0)
            {
                res[y] -= oddParents[i] - evenParents[i];
            }
            else
            {
                (*baseSet).insert(y);
                newAdditions.insert(y);
            }
        }
    }
    for (ll x : newAdditions) (*baseSet).erase(x);
    set<ll> done;
    for (ll j = 0; j < childrenSets.size(); j++)
    {
        if (j == index) continue;
        for (auto y : *childrenSets[j])
        {
            if ((*baseSet).count(y) > 0)
            {
                (*baseSet).erase(y);
                done.insert(y);
                res[y] += evenParents[i] - oddParents[i];
            }
            else
            {
                (*baseSet).insert(y);
                if (done.count(y) > 0)
                    res[y] += oddParents[i] - evenParents[i];
            }
        }
    }
    return baseSet;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N, Q;
    cin >> N >> Q;
    vv graph(N);
    for (ll i = 0; i < N - 1; i++)
    {
        ll a, b;
        cin >> a >> b; a--; b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    ll root = 0;
    while (graph[root].size() == 1) root++;
    v leafCount(N, -1);
    getLeafCount(root, graph, leafCount);
    v oddParents(N, -1), evenParents(N, -1);
    getOddAndEvenParents(root, graph, oddParents, evenParents, 0, 0, leafCount);
    vv queries(Q);
    for (ll i = 0; i < Q; i++)
    {
        ll amt;
        cin >> amt;
        for (ll j=  0; j < amt; j++)
        {
            ll par;
            cin >> par;
            par--;
            queries[i].pb(par);
        }
    }
    vv changedInQueries(N);
    for (ll i = 0 ;i < Q; i++)
    {
        map<ll, ll> changed;
        
        for (ll x : queries[i])
        {
            changed[x]++;
        }
        for (auto x : changed)
        {
            if ((x.s % 2 == 1) ^ (graph[x.f].size() == 1)) changedInQueries[x.f].pb(i);
        }
    }
    v addToQuery(Q);
    ll base = N - 2;
    for (ll i = 0 ;i < N; i++) if (leafCount[i] % 2 == 0) base++;
    vb visited(N, false);
    solve(root, graph, visited, addToQuery, changedInQueries, oddParents, evenParents);
    for (ll i = 0; i < Q; i++)
    {
        ll count = leafCount[root] + queries[i].size();
        set<ll> changed;
        for (ll x : queries[i]) if (graph[x].size() == 1) changed.insert(x);
        count -= changed.size();
        if (count % 2 == 1) cout << "-1\n";
        else cout << base + queries[i].size() + addToQuery[i] << "\n";
    }
    return 0;
}

Compilation message

cleaning.cpp:28:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   28 | const ll INF = 1e18;
      |                ^~~~
cleaning.cpp: In function 'std::set<int>* solve(ll, vv&, vb&, v&, vv&, v&, v&)':
cleaning.cpp:72:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (ll i = 0; i < childrenSets.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:74:39: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   74 |         if ((*childrenSets[i]).size() > maxiSize)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
cleaning.cpp:82:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:100:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 19752 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1748 KB Output is correct
2 Correct 15 ms 1748 KB Output is correct
3 Correct 34 ms 23112 KB Output is correct
4 Correct 70 ms 20780 KB Output is correct
5 Correct 86 ms 27564 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3540 KB Output is correct
2 Correct 13 ms 3612 KB Output is correct
3 Correct 60 ms 53584 KB Output is correct
4 Correct 86 ms 51884 KB Output is correct
5 Correct 53 ms 48560 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 81360 KB Output is correct
2 Correct 38 ms 8796 KB Output is correct
3 Correct 9 ms 4700 KB Output is correct
4 Correct 119 ms 35744 KB Output is correct
5 Correct 204 ms 61776 KB Output is correct
6 Correct 301 ms 79440 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 44172 KB Output is correct
2 Correct 151 ms 33364 KB Output is correct
3 Correct 116 ms 23712 KB Output is correct
4 Correct 156 ms 34896 KB Output is correct
5 Correct 151 ms 33892 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 83792 KB Output is correct
2 Execution timed out 1042 ms 229532 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 19752 KB Output is correct
3 Correct 15 ms 1748 KB Output is correct
4 Correct 15 ms 1748 KB Output is correct
5 Correct 34 ms 23112 KB Output is correct
6 Correct 70 ms 20780 KB Output is correct
7 Correct 86 ms 27564 KB Output is correct
8 Correct 13 ms 3540 KB Output is correct
9 Correct 13 ms 3612 KB Output is correct
10 Correct 60 ms 53584 KB Output is correct
11 Correct 86 ms 51884 KB Output is correct
12 Correct 53 ms 48560 KB Output is correct
13 Correct 351 ms 81360 KB Output is correct
14 Correct 38 ms 8796 KB Output is correct
15 Correct 9 ms 4700 KB Output is correct
16 Correct 119 ms 35744 KB Output is correct
17 Correct 204 ms 61776 KB Output is correct
18 Correct 301 ms 79440 KB Output is correct
19 Correct 176 ms 44172 KB Output is correct
20 Correct 151 ms 33364 KB Output is correct
21 Correct 116 ms 23712 KB Output is correct
22 Correct 156 ms 34896 KB Output is correct
23 Correct 151 ms 33892 KB Output is correct
24 Correct 468 ms 83792 KB Output is correct
25 Execution timed out 1042 ms 229532 KB Time limit exceeded
26 Halted 0 ms 0 KB -