oj.uz

Submission #1046646

# Submission time Handle Problem Language Result Execution time Memory
1046646 2024-08-06T19:41:36 Z beaconmc Spring cleaning (CEOI20_cleaning) C++14
17 / 100
 1000 ms 49416 KB 
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
vector<ll> edges[200005];
vector<ll> vtree[200005];
ll realans = 0;
ll vals[200005];
ll contrib[200005];
ll depth[200005];
ll par[200005];
ll tin[200005];
ll timer = 0;
map<ll, ll> lmao;

ll lmfao = 0;
 
int dp(ll a, ll p){
    tin[a] = timer++;
    par[a] = p;
    ll ans = 0;
    if (edges[a].size() <= 1) ans = 1;
    for (auto&i : edges[a]){
        if (i != p) ans += dp(i, a);
    }       
    if (p!=-1) realans += 1 + (ans+1)%2;
 
    if (p != -1) vals[a] = 1 + (ans+1)%2;

    return 1 + (ans+1)%2;
}
void dp2(ll a, ll p, ll d){


    depth[a] = d;

    if (p==-1) contrib[a] = 0;
    if (p != -1){
        contrib[a] = contrib[par[a]] + vals[a]; 
    }


    for (auto&i : edges[a]){
        if (i != p) dp2(i, a, d+1);
        
    }

}
ll dp3(ll a, ll p){

    ll tot = lmao[a];
    for (auto&i : vtree[a]) if (i != p) tot += dp3(i, a);


    lmfao += (tot/2)*2 * -(depth[a]*3 - contrib[a]*2);
    return tot;
}

int anc[200005][30];

int ancc(ll a, ll x){

    if (par[a] == -1) return a;

    if (x==0) return par[a];

    if (anc[a][x] != -1) return anc[a][x];

    else{
        return anc[a][x] = ancc(ancc(a,x-1),x-1);
    }
}

int lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);


    FORNEG(i,29,-1) if (depth[ancc(a, i)] >= depth[b]) a = ancc(a,i);

    if (a==b) return a;

    FORNEG(i,29,-1) if (ancc(a,i) != ancc(b,i)) a = ancc(a,i), b = ancc(b,i);
    return par[a];
}

int main(){
    FOR(i,0,200005) FOR(j,0,30) anc[i][j] = -1;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,q;
    cin >> n >> q;
    FOR(i,0,n-1){
        ll a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    ll root = -1;
    ll cnt = 0;
    FOR(j,1,n+1){
        if (edges[j].size() != 1){
            root = j;
        }else{
            cnt++;
        }
    }

    dp(root, -1);
    dp2(root, -1, 0);



    ll ans = 0;
    FOR(i,1,n+1) ans += vals[i];
    
 
    FOR(i,0,q){
        ll d; cin >> d;
        ll cur = n+1;
        ll curans = 0;
        set<ll> used;
        ll newleaves=0;
        lmao.clear();
        vector<vector<ll>> stuff;
        lmfao = 0;
        

        FOR(k,0,d){
            ll temp; cin >> temp;
            used.insert(temp);
            curans++;
            if (edges[temp].size() == 1)continue;
            newleaves++;
            stuff.push_back({tin[temp], temp});
            curans += depth[temp]*3 - contrib[temp]*2;
            lmao[temp] += 1;
        }
        sort(stuff.begin(), stuff.end());
        set<vector<ll>> stuff2;
        FOR(i,1,stuff.size()){
            ll lcatemp = lca(stuff[i][1], stuff[i-1][1]);

            stuff2.insert({tin[lcatemp], lcatemp});
        }

        if (stuff.size()){
            ll lcatemp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
            stuff2.insert({tin[lcatemp], lcatemp});
        }
        for (auto&i : stuff)stuff2.insert(i);

        vector<ll> stack;
        for (auto&k : stuff2){
            while (stack.size() && lca(stack[stack.size()-1], k[1]) != stack[stack.size()-1]) stack.pop_back();
            if (stack.size()) vtree[stack[stack.size()-1]].push_back(k[1]);
            stack.push_back(k[1]);
        }



        for (auto&k : stuff2){
            if (vtree[k[1]].size() != 0){
                dp3(k[1], -1);
                break;
            }
        }



 
 
        if ((cnt+newleaves)%2==1) cout << -1 << "\n";
        else{
            cout << ans+curans+lmfao << "\n";
        }
        for (auto&i : stuff) vtree[i[1]].clear();
        for (auto&i : used){
            while (edges[i].size() && edges[i][edges[i].size()-1]>n){
                edges[i].pop_back();
            }
        }
 
    }
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:4:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  144 |         FOR(i,1,stuff.size()){
      |             ~~~~~~~~~~~~~~~~     
cleaning.cpp:144:9: note: in expansion of macro 'FOR'
  144 |         FOR(i,1,stuff.size()){
      |         ^~~
cleaning.cpp:123:12: warning: unused variable 'cur' [-Wunused-variable]
  123 |         ll cur = n+1;
      |            ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 41048 KB Output is correct
2 Execution timed out 1091 ms 42540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 41564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 48912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 43108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 45452 KB Output is correct
2 Execution timed out 1018 ms 44884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 47184 KB Output is correct
2 Correct 83 ms 49416 KB Output is correct
3 Correct 86 ms 48344 KB Output is correct
4 Correct 106 ms 48464 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 41048 KB Output is correct
2 Execution timed out 1091 ms 42540 KB Time limit exceeded
3 Halted 0 ms 0 KB -