oj.uz

Submission #985319

# Submission time Handle Problem Language Result Execution time Memory
985319 2024-05-17T15:02:54 Z alexdd Spring cleaning (CEOI20_cleaning) C++17
0 / 100
 244 ms 14204 KB 
#include<bits/stdc++.h>
using namespace std;
int n,q,root;
vector<int> con[100005];

struct node
{
    int cnt0,cnt1;
    int lazy;
};
node aint[270000];
void propagate(int nod)
{
    if(!aint[nod].lazy)
        return;
    aint[nod*2].lazy ^= 1;
    aint[nod*2+1].lazy ^= 1;
    swap(aint[nod*2].cnt0, aint[nod*2].cnt1);
    swap(aint[nod*2+1].cnt0, aint[nod*2+1].cnt1);
    aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].lazy ^= 1;
        swap(aint[nod].cnt0, aint[nod].cnt1);
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri));
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri);
    aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0;
    aint[nod].cnt1 = aint[nod*2].cnt1 + aint[nod*2+1].cnt1;
}

int siz[100005];
int cntf[100005];
int head[100005];
int parent[100005];
int depth[100005];
int pos[100005],curpos;

void dfs(int nod)
{
    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            depth[adj]=depth[nod]+1;
            dfs(adj);
            cntf[nod] += cntf[adj];
            siz[nod] += siz[adj];
        }
    }
    if(cntf[nod]==0) cntf[nod]=1;
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    head[nod]=chead;
    int heavy=-1,maxc=-1;
    for(auto adj:con[nod])
        if(adj!=parent[nod] && siz[adj]>maxc)
            maxc=siz[adj], heavy=adj;
    if(heavy!=-1)
        decompose(heavy,chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decompose(adj,adj);
}
void hld_upd(int a)
{
    for(;head[a]!=root;a=parent[head[a]])
    {
        upd(1,1,n,pos[head[a]],pos[a]);
    }
    upd(1,1,n,pos[root],pos[a]);
}
int aux[100005];
int visited[100005];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod].cnt0=1;
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if((int)con[i].size()>1)
        {
            root=i;
            break;
        }
    }
    dfs(root);
    decompose(root,root);
    build(1,1,n);
    for(int i=1;i<=n;i++)
        if(cntf[i]%2==1)
            upd(1,1,n,pos[i],pos[i]);
    for(int pas=1;pas<=q;pas++)
    {
        int nr,auxf=0;
        cin>>nr;
        for(int i=1;i<=nr;i++)
        {
            cin>>aux[i];
            hld_upd(aux[i]);
            if(cntf[aux[i]]==1 && visited[aux[i]]!=pas)
                visited[aux[i]]=pas;
            else
                auxf++;
        }
        if((cntf[root]+auxf)%2==1) cout<<-1<<"\n";
        else cout<<aint[1].cnt0*2 + aint[1].cnt1 - 2 + nr<<"\n";
        for(int i=1;i<=nr;i++)
            hld_upd(aux[i]);
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Incorrect 139 ms 8568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Incorrect 139 ms 8568 KB Output isn't correct
3 Halted 0 ms 0 KB -