oj.uz

Submission #866001

# Submission time Handle Problem Language Result Execution time Memory
866001 2023-10-25T09:34:26 Z danikoynov Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 ms 18976 KB 
#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 sub[maxn], parent[maxn];
ll depth[maxn];
void calc(int v, int par)
{
    sub[v] = 1;
    parent[v] = par;
    for (int u : adj[v])
    {
        if (u == par)
            continue;
        depth[u] = depth[v] + 1;
        calc(u, v);
        sub[v] += sub[u];
    }
}   
 
int find_centroid(int v, int par, int sz)
{
    for (int u : adj[v])
    {
        if (u == par)
            continue;
 
        if (sub[u] > sz / 2)
        {
            return find_centroid(u, v, sz);
        }
    }
 
    return v;
}
 
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; 

}
 
int used[maxn];
 
void answer_queries()
{
    int root = 1;
    while(adj[root].size() == 1)
        root ++;
    calc(root, -1);
 
    for (int i = 1; i <= q; i ++)
    {
        int d;
        cin >> d;
        for (int j = 1; j <= d; j ++)
        {
            int par;
            cin >> par;
            added[par] ++;
        }
 
        
        find_depths(root);
      
        if (cnt[root] % 2 == 1)
            cout << -1 << endl;
        else
            cout << sum[root] << endl;
    }
 
 
}
 
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 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
 
3 1
1 2
1 3
6 3 3 3 2 2 2
 
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Execution timed out 1090 ms 8016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7260 KB Output is correct
2 Correct 6 ms 7260 KB Output is correct
3 Correct 22 ms 11376 KB Output is correct
4 Correct 19 ms 10448 KB Output is correct
5 Correct 25 ms 11508 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7772 KB Output is correct
2 Correct 7 ms 7772 KB Output is correct
3 Correct 37 ms 18976 KB Output is correct
4 Correct 37 ms 18236 KB Output is correct
5 Correct 28 ms 17744 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 8788 KB Output is correct
2 Correct 130 ms 8020 KB Output is correct
3 Correct 190 ms 7780 KB Output is correct
4 Correct 222 ms 8280 KB Output is correct
5 Correct 192 ms 8508 KB Output is correct
6 Correct 225 ms 8540 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 9612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 11088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Execution timed out 1090 ms 8016 KB Time limit exceeded
3 Halted 0 ms 0 KB -