oj.uz

Submission #1002386

# Submission time Handle Problem Language Result Execution time Memory
1002386 2024-06-19T13:59:03 Z yoav_s Spring cleaning (CEOI20_cleaning) C++17
53 / 100
 1000 ms 40912 KB 
#include <bits/stdc++.h>

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:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 73 ms 4124 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1488 KB Output is correct
2 Correct 14 ms 1492 KB Output is correct
3 Correct 37 ms 16448 KB Output is correct
4 Correct 79 ms 16448 KB Output is correct
5 Correct 92 ms 19528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3028 KB Output is correct
2 Correct 13 ms 2960 KB Output is correct
3 Correct 59 ms 40276 KB Output is correct
4 Correct 78 ms 40912 KB Output is correct
5 Correct 65 ms 36588 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7000 KB Output is correct
2 Correct 24 ms 2648 KB Output is correct
3 Correct 8 ms 2140 KB Output is correct
4 Correct 21 ms 4784 KB Output is correct
5 Correct 31 ms 5468 KB Output is correct
6 Correct 64 ms 5248 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 14416 KB Output is correct
2 Correct 103 ms 8272 KB Output is correct
3 Correct 80 ms 4924 KB Output is correct
4 Correct 96 ms 8276 KB Output is correct
5 Correct 103 ms 8192 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 22180 KB Output is correct
2 Execution timed out 1057 ms 29784 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 344 KB Output is correct
2 Correct 73 ms 4124 KB Output is correct
3 Correct 14 ms 1488 KB Output is correct
4 Correct 14 ms 1492 KB Output is correct
5 Correct 37 ms 16448 KB Output is correct
6 Correct 79 ms 16448 KB Output is correct
7 Correct 92 ms 19528 KB Output is correct
8 Correct 13 ms 3028 KB Output is correct
9 Correct 13 ms 2960 KB Output is correct
10 Correct 59 ms 40276 KB Output is correct
11 Correct 78 ms 40912 KB Output is correct
12 Correct 65 ms 36588 KB Output is correct
13 Correct 70 ms 7000 KB Output is correct
14 Correct 24 ms 2648 KB Output is correct
15 Correct 8 ms 2140 KB Output is correct
16 Correct 21 ms 4784 KB Output is correct
17 Correct 31 ms 5468 KB Output is correct
18 Correct 64 ms 5248 KB Output is correct
19 Correct 108 ms 14416 KB Output is correct
20 Correct 103 ms 8272 KB Output is correct
21 Correct 80 ms 4924 KB Output is correct
22 Correct 96 ms 8276 KB Output is correct
23 Correct 103 ms 8192 KB Output is correct
24 Correct 211 ms 22180 KB Output is correct
25 Execution timed out 1057 ms 29784 KB Time limit exceeded
26 Halted 0 ms 0 KB -