Submission #866088

#	Time	Username	Problem	Language	Result	Execution time	Memory
866088		danikoynov	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	109 ms	40864 KiB

cleaning

#include<bits/stdc++.h>
#define endl '\n'
    
using namespace std;
typedef long long ll;
    
const int maxn = 1e5 + 10;
    
int n, q;
vector < int > adj[maxn];
    
void input()
{
    cin >> n >> q;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
}
    
int find_leaves(int v, int par)
{
    int cnt = 0, children = 0;
    for (int u : adj[v])
    {
        if (u == par)
            continue;
        cnt += find_leaves(u, v);
        children ++;
    }
    
    if (par == -1 && children == 1)
        cnt ++;
    if (children == 0)
        cnt ++;
    return cnt;
}
    
int parent[maxn], is_leaf[maxn];
int tin[maxn], tout[maxn], timer, occ[2 * maxn];
ll depth[maxn];
    
void calc(int v, int par)
{
    occ[++ timer] = v;
    tin[v] = timer;

    parent[v] = par;
    is_leaf[v] = true;
    for (int u : adj[v])
    {
        if (u == par)
            continue;
        is_leaf[v] = false;
        depth[u] = depth[v] + 1;
        calc(u, v);

        occ[++ timer] = v;
    }
    
    tout[v] = timer;
}   
    
    
const int maxlog = 21;
int dp[maxlog][maxn * 2], lg[2 * maxn];
    
void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }
    
    for (int j = 1; j < maxlog; j ++)
        for (int i = 1; i <= (timer - (1 << j)) + 1; i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}
    
int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1, lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}
    
ll get_distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}
 
ll added[maxn];
ll sum[maxn], cnt[maxn];
int all = 0;
void find_depths(int v)
{
    all ++;
    sum[v] = cnt[v] = 0;
    bool leaf = true;
    for (int u : adj[v])
    {   
        if (u == parent[v])
            continue;
        find_depths(u);
        cnt[v] += cnt[u];
        sum[v] += sum[u];
        leaf = false;
    }
    
    sum[v] = sum[v] + added[v] * (depth[v] + 1);
    cnt[v] += added[v];
    
    if (leaf && added[v] == 0)
        sum[v] = sum[v] + depth[v], cnt[v] ++;
    
    ll pairs = cnt[v] / 2;
    if (pairs * 2 == cnt[v])
        pairs --;
    
    sum[v] = sum[v] - pairs * depth[v] * (ll)2;
    cnt[v] -= pairs * 2;
    added[v] = 0;
    //cout << "state " << v << " " << cnt_leaves << " " << ans << endl; 
    
}
    
ll sub[maxn];
void dfs(int v)
{
    sub[v] = 0;
    int child = 0;
    for (int u : adj[v])
    {
        if (u == parent[v])
            continue;
        dfs(u);
        sub[v] = sub[v] + sub[u];
        child ++;
    }

    if (child == 0)
        sub[v] = 1;
}

bool cmp(int v, int u)
{
    return tin[v] < tin[u];
}

ll c1[maxn], c2[maxn];

vector < int > vir[maxn];
ll cnt_on[maxn];

pair < ll, ll > vir_dfs(int v, int par)
{
   
    ll cnt = 0, sum = 0;
    for (int u : vir[v])
    {
        pair < ll, ll > res = vir_dfs(u, v);
        cnt += res.second;
        sum += res.first;
    }

    cnt = cnt + cnt_on[v];
    cnt %= 2;
    if (cnt == 1 && par != -1)
    {
        //cout << c1[v] << " : " << c1[par] << endl;
        //cout << c2[v] << " : " << c2[par] << endl;
        ll d1 = c1[v] - c1[par];
        ll d2 = c2[v] - c2[par];
        sum = sum + d1 - d2;
    }
    
    ///cout << v << " : " << sum << " : " << cnt << endl;
    return {sum, cnt}; 
}

ll virtual_tree(vector < int > nodes, int root)
{

    if (nodes.empty())
        return 0;
    for (int cur : nodes)
        cnt_on[cur] ++;
    nodes.push_back(root);
    sort(nodes.begin(), nodes.end(), cmp);
    vector < int > nc;
    for (int i = 1; i < nodes.size(); i ++)
    {
        ///cout << get_lca(nodes[i - 1], nodes[i]) << " " << nodes[i - 1] << " " << nodes[i] << endl;
        nc.push_back(get_lca(nodes[i - 1], nodes[i]));
    }
    for (int cur : nc)
        nodes.push_back(cur);
    nc.clear();

    
    sort(nodes.begin(), nodes.end());
    
    for (int cur : nodes)
    {
        if (nc.empty() || cur != nc.back())
            nc.push_back(cur);
    }
    nodes = nc;
    sort(nodes.begin(), nodes.end(), cmp);

    for (int cur : nodes)
        vir[cur].clear();

    vector < int > st;
    for (int i = 0; i < nodes.size(); i ++)
    {
        ///cout << nodes[i] << " ";
        while (!st.empty() && get_lca(nodes[i], st.back()) != st.back())
            st.pop_back();
        if (!st.empty())
        {
            ///cout << "edge " << st.back() << " " << nodes[i] << endl;
            vir[st.back()].push_back(nodes[i]);
        }
        st.push_back(nodes[i]);
    }
    

    ll ans = vir_dfs(st[0], -1).first;

    for (int cur : nodes)
        cnt_on[cur] = 0;
    
    
    return ans;

}

void push_down(int v)
{
    if (sub[v] % 2 == 1)
        c1[v] ++;
    else
        c2[v] ++;
    
    for (int u : adj[v])
    {
        if (u == parent[v])
            continue;
        c1[u] = c1[v];
        c2[u] = c2[v];
        push_down(u);
    }
}
void answer_queries()
{
    int root = 1;
    while(adj[root].size() == 1)
        root ++;
    calc(root, -1);
    build_sparse_table();
    
    dfs(root);
    push_down(root);
    int sum = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (i == root)
            continue;

        if (sub[i] % 2 == 0)
            sum += 2;
        else
            sum ++;
    }
    ///cout << sum << endl;
    for (int i = 1; i <= q; i ++)
    {
        int d;
        cin >> d;
        set < int > nodes;
        for (int j = 0; j < d; j ++)
        {
            int x;
            cin >> x;
            nodes.insert(x);
            added[x] ++;
        }

        ll ans = d + sum;

        vector < int > attach;
        for (int cur : nodes)
        {
            if (is_leaf[cur])
                added[cur] --;
        
            added[cur] %= 2;
            if (added[cur] > 0)
            {
                attach.push_back(cur);
            }
        }
        

        if ((sub[root] % 2 + attach.size()) % 2 == 1) 
        { 
            cout << -1 << endl;   
        }
        else
        {

            cout << ans +virtual_tree(attach, root)<< endl;
        }
        for (int cur : nodes)
        {
            added[cur] = 0;
        }
    }

 
    
    
}
    
void solve()
{
    input();
    answer_queries();
}
    
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    solve();
    return 0;
}
    
/**
 7 4
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
4 1 1 3 5
    
4 1
1 2
1 3
1 4
8 3 3 3 2 2 2 4 4
    
    15 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
4 4 5 3 7
*/

Compilation message (stderr)

cleaning.cpp: In function 'll virtual_tree(std::vector<int>, int)':
cleaning.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     for (int i = 1; i < nodes.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
cleaning.cpp:227:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |     for (int i = 0; i < nodes.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~

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