oj.uz

Submission #1002393

# Submission time Handle Problem Language Result Execution time Memory
1002393 2024-06-19T14:08:10 Z yoav_s Spring cleaning (CEOI20_cleaning) C++17
53 / 100
 699 ms 262144 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;
#define set unordered_set

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::unordered_set<int>* solve(ll, vv&, vb&, v&, vv&, v&, v&)':
cleaning.cpp:73:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (ll i = 0; i < childrenSets.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:75:39: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   75 |         if ((*childrenSets[i]).size() > maxiSize)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
cleaning.cpp:83:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:101:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::unordered_set<int>*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (ll j = 0; j < childrenSets.size(); j++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 20620 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2260 KB Output is correct
2 Correct 14 ms 2260 KB Output is correct
3 Correct 34 ms 23900 KB Output is correct
4 Correct 69 ms 25120 KB Output is correct
5 Correct 82 ms 31912 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4820 KB Output is correct
2 Correct 16 ms 4772 KB Output is correct
3 Correct 87 ms 64464 KB Output is correct
4 Correct 124 ms 67788 KB Output is correct
5 Correct 105 ms 57684 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 80440 KB Output is correct
2 Correct 29 ms 10076 KB Output is correct
3 Correct 10 ms 5212 KB Output is correct
4 Correct 87 ms 35260 KB Output is correct
5 Correct 164 ms 58196 KB Output is correct
6 Correct 232 ms 78288 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 48252 KB Output is correct
2 Correct 117 ms 37452 KB Output is correct
3 Correct 105 ms 25528 KB Output is correct
4 Correct 155 ms 38588 KB Output is correct
5 Correct 116 ms 37968 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 90680 KB Output is correct
2 Runtime error 699 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 20620 KB Output is correct
3 Correct 12 ms 2260 KB Output is correct
4 Correct 14 ms 2260 KB Output is correct
5 Correct 34 ms 23900 KB Output is correct
6 Correct 69 ms 25120 KB Output is correct
7 Correct 82 ms 31912 KB Output is correct
8 Correct 16 ms 4820 KB Output is correct
9 Correct 16 ms 4772 KB Output is correct
10 Correct 87 ms 64464 KB Output is correct
11 Correct 124 ms 67788 KB Output is correct
12 Correct 105 ms 57684 KB Output is correct
13 Correct 241 ms 80440 KB Output is correct
14 Correct 29 ms 10076 KB Output is correct
15 Correct 10 ms 5212 KB Output is correct
16 Correct 87 ms 35260 KB Output is correct
17 Correct 164 ms 58196 KB Output is correct
18 Correct 232 ms 78288 KB Output is correct
19 Correct 127 ms 48252 KB Output is correct
20 Correct 117 ms 37452 KB Output is correct
21 Correct 105 ms 25528 KB Output is correct
22 Correct 155 ms 38588 KB Output is correct
23 Correct 116 ms 37968 KB Output is correct
24 Correct 347 ms 90680 KB Output is correct
25 Runtime error 699 ms 262144 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -