Submission #644344

#	Time	Username	Problem	Language	Result	Execution time	Memory
644344		Itamar	Spring cleaning (CEOI20_cleaning)	C++14	0 / 100	1095 ms	8816 KiB

cleaning

// CEOI.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
#define ll long long
#include <vector>
#define vll vector<ll>
#define vi vector<int>
const int m = 1e9 + 7;
ll c(ll x) {
    return ((x * (x - 1)) / 2) % m;
}
const int siz = 1e5;
vector<vi> fr(siz);
vi padre(siz);
vi l(siz);
vll d(siz);
int n;
int dfs(int i) {
    if (i >= n)
        return 1;
    int ans = 0;
    for (int f : fr[i]) {
        if (f != padre[i]) {
            padre[f] = i;
            ans += dfs(f);
        }
    }
    if (fr[i].size() == 1)
        ans++;
    l[i] = ans;
    return ans;
}
ll dfs1(int i, ll dis, int pad) {
    if (i >= n)
        return dis;
    if ( fr[i].size() == 1) {
        d[i] = dis;
        return dis;
    }
    ll sum = 0;
    for (int f : fr[i]) {
        if (f != pad) {
            sum += dfs1(f, dis + 1, i);
        }
    }
    d[i] = sum;
    return sum;
}
int main()
{
    int q;
    cin >> n >> q;
    int liv = 0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        fr[a].push_back(b);
        fr[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
        if (fr[i].size() == 1)
            liv++;
    }
    int idx = n;
    for (int i = 0; i < q; i++) {
        int di;
        cin >> di;
        vi re;
        liv += di;
        for (int j = 0; j < di; j++) {
            int x;
            cin >> x;
            x--;
            if (fr[x].size() == 1)
                liv--;
            fr[x].push_back(++idx);
            re.push_back(x);
        }
        if (liv % 2 == 0) {
            dfs(0);
            int v = 0;
            int num = l[v];
            while (true) {
                int in = -1;
                int ma = 0;
                for (int f : fr[v]) {
                    if (l[f] > ma && f != padre[v]) {
                        in = f;
                        ma = l[f];
                    }
                }
                if (ma > num / 2)
                    v = in;
                else break;
            }

            cout << dfs1(v, 0, v) << "\n";
        }
        else {
            cout << -1 << "\n";
        }
        for (int x : re) {
            fr[x].pop_back();
            if (fr[x].size() == 1)
                liv++;
        }
        liv -= di;
        idx = n;
    }
   
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30