oj.uz

Submission #1002387

# Submission time Handle Problem Language Result Execution time Memory
1002387 2024-06-19T13:59:57 Z yoav_s Spring cleaning (CEOI20_cleaning) C++17
53 / 100
 1000 ms 41160 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(set<ll>());
    for (ll x : changes[i])
    {
        childrenSets.back().insert(x);
        res[x] += oddParents[i] - evenParents[i];
    }
    sort(all(childrenSets),[](set<ll> &a, set<ll> &b){return a.size() < b.size();});
    set<ll> baseSet;
    if (childrenSets.size() > 0)
    {
        baseSet = childrenSets.back();
        childrenSets.pop_back();
    }
    set<ll> newAdditions;
    for (auto &x : childrenSets)
    {
        for (auto y : x)
        {
            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 (auto &x : childrenSets)
    {
        for (auto y : x)
        {
            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;
      |                ^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1748 KB Output is correct
2 Correct 15 ms 2000 KB Output is correct
3 Correct 38 ms 17276 KB Output is correct
4 Correct 67 ms 17560 KB Output is correct
5 Correct 83 ms 20808 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3280 KB Output is correct
2 Correct 13 ms 3284 KB Output is correct
3 Correct 55 ms 40024 KB Output is correct
4 Correct 76 ms 41160 KB Output is correct
5 Correct 47 ms 36176 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7516 KB Output is correct
2 Correct 30 ms 3152 KB Output is correct
3 Correct 10 ms 2392 KB Output is correct
4 Correct 20 ms 4700 KB Output is correct
5 Correct 30 ms 5464 KB Output is correct
6 Correct 64 ms 5464 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15824 KB Output is correct
2 Correct 108 ms 9556 KB Output is correct
3 Correct 90 ms 5968 KB Output is correct
4 Correct 114 ms 9808 KB Output is correct
5 Correct 107 ms 9628 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23820 KB Output is correct
2 Execution timed out 1030 ms 31052 KB Time limit exceeded
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 70 ms 4824 KB Output is correct
3 Correct 13 ms 1748 KB Output is correct
4 Correct 15 ms 2000 KB Output is correct
5 Correct 38 ms 17276 KB Output is correct
6 Correct 67 ms 17560 KB Output is correct
7 Correct 83 ms 20808 KB Output is correct
8 Correct 16 ms 3280 KB Output is correct
9 Correct 13 ms 3284 KB Output is correct
10 Correct 55 ms 40024 KB Output is correct
11 Correct 76 ms 41160 KB Output is correct
12 Correct 47 ms 36176 KB Output is correct
13 Correct 63 ms 7516 KB Output is correct
14 Correct 30 ms 3152 KB Output is correct
15 Correct 10 ms 2392 KB Output is correct
16 Correct 20 ms 4700 KB Output is correct
17 Correct 30 ms 5464 KB Output is correct
18 Correct 64 ms 5464 KB Output is correct
19 Correct 110 ms 15824 KB Output is correct
20 Correct 108 ms 9556 KB Output is correct
21 Correct 90 ms 5968 KB Output is correct
22 Correct 114 ms 9808 KB Output is correct
23 Correct 107 ms 9628 KB Output is correct
24 Correct 216 ms 23820 KB Output is correct
25 Execution timed out 1030 ms 31052 KB Time limit exceeded
26 Halted 0 ms 0 KB -