oj.uz

Submission #866013

# Submission time Handle Problem Language Result Execution time Memory
866013 2023-10-25T09:50:48 Z vnm06 Roads (CEOI20_roads) C++14
0 / 100
 16 ms 25692 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int n, q, kor=0, brl=0, ans=0, par[300005];
vector<int> gr[300005];
bool used[300005];
int lst[300005], gol[300005];

void dfs(int v)
{
    gol[v]=1;
    used[v]=1;
    int brs=gr[v].size();
    if(brs==1) {brl++; lst[v]=1;}
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(used[nv]) continue;
        par[nv]=v;
        dfs(nv);
        lst[v]+=lst[nv];
        gol[v]+=gol[nv];
    }
    if(v!=kor && !(lst[v]&1)) ans++;
}

int nvt[300005];

int brchains=1, tv=0;
int chain[300005][2];
int to_chain[300005];
int red[300005], pos[300005];
int stojnost[300005];


void create_hld(int v)
{
    tv++;
    red[tv]=v;
    pos[v]=tv;
    to_chain[v]=brchains;
    int brs=gr[v].size();
    if(!brs) return;
    create_hld(gr[v][0]);
    for(int i=1; i<brs; i++)
    {
        chain[brchains][1]=tv;
        chain[brchains+1][0]=tv+1;
        brchains++;
        create_hld(gr[v][i]);
    }
}

bool promlst[300005];
bool osob[300005];

int tree[2000005];
int lazy[2000005];

void push_lazy(int v, int le, int ri)
{
    if(!lazy[v]) return;
    tree[v]=(ri-le+1)-tree[v];
    if(le!=ri) {lazy[2*v]^=1; lazy[2*v+1]^=1;}
    lazy[v]=0;
}

void update(int v, int le, int ri, int be, int en)
{
    push_lazy(v, le, ri);
    if(le>en || ri<be) return;
    if(be<=le && ri<=en)
    {
        lazy[v]^=1;
        push_lazy(v, le, ri);
        return;
    }
    int mid=(le+ri)/2;
    update(2*v, le, mid, be, en);
    update(2*v+1, mid+1, ri, be, en);
    tree[v]=tree[2*v]+tree[2*v+1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>q;
    for(int i=0; i<n-1; i++)
    {
        int a, b;
        cin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    for(int i=1; i<=n; i++) if(gr[i].size()>1 && !kor) kor=i;
    dfs(kor);

    for(int i=1; i<=n; i++)
    {
        int brs=gr[i].size();
        if(i==kor) brs++;
        for(int j=0; j<brs-1; j++)
        {
            int nv=gr[i][j];
            if(par[i]==nv) swap(gr[i][j], gr[i][brs-1]);
            else if(gol[nv]>gol[gr[i][0]]) swap(gr[i][j], gr[i][0]);
        }
        gr[i].resize(brs-1);
    }
    /**
    for(int i=1; i<=n; i++)
    {
        cout<<"Vryh "<<i<<": {";
        for(int j=0; j<gr[i].size(); j++) cout<<gr[i][j]<<" ";
        cout<<"}\n";
    }*/
    chain[1][0]=1;
    create_hld(kor);
    chain[brchains][1]=n;

    /**
    for(int i=1; i<=n; i++) cout<<red[i]<<" ";
    cout<<endl<<brchains<<endl;
    for(int i=1; i<=brchains; i++) cout<<chain[i][0]<<" "<<chain[i][1]<<endl;
    for(int i=1; i<=n; i++) cout<<pos[i]<<" ";
    cout<<endl;
    for(int i=1; i<=n; i++) cout<<to_chain[i]<<" ";
    cout<<endl;*/

    for(int i=1; i<=n; i++)
    {
        if(i!=kor && !(lst[i]&1)) {update(1, 1, n, pos[i], pos[i]);}
    }
    for(int i=0; i<q; i++)
    {
        int d, brl=lst[kor];
        cin>>d;
        brl+=d;
        for(int i=0; i<d; i++)
        {
            cin>>nvt[i];
            if(nvt[i]==kor) continue;
            if(!promlst[nvt[i]] && !gr[nvt[i]].size())
            {
                brl--;
                promlst[nvt[i]]=1;
                osob[i]=1;
                continue;
            }
            int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i];
            while(tekchain!=1)
            {
                int lpos=chain[tekchain][0];
               /// cout<<lpos<<" "<<tpos<<endl;
                update(1, 1, n, lpos, tpos);
                tv=par[red[lpos]];
                tpos=pos[tv];
                tekchain=to_chain[tv];
            }
            if(tpos>1) update(1, 1, n, 2, tpos);
        }
        if(brl&1) cout<<-1<<endl;
        else cout<<n-1+d+tree[1]<<endl;
        for(int i=0; i<d; i++)
        {
            promlst[nvt[i]]=0;
            if(nvt[i]==kor || osob[i]) 
            {
                osob[i]=0;
                continue;
            }
            osob[i]=0;
            int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i];
            while(tekchain!=1)
            {
                int lpos=chain[tekchain][0];
                update(1, 1, n, lpos, tpos);
                tv=par[red[lpos]];
                tpos=pos[tv];
                tekchain=to_chain[tv];
            }
            if(tpos>1) update(1, 1, n, 2, tpos);
        }
    }
    return 0;
}
/*
12 3
1 3
4 1
9 1
8 3
3 7
10 2
11 2
2 6
4 5
4 6
9 12
3 1 4 7
2 5 8
1 12


7 4
1 2
2 4
4 5
5 6
5 7
3 4
1 7
1 4
2 2 4
1 1
*/

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 25688 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 17244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 17244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 17244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 25692 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 25692 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -