oj.uz

답안 #866015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866015 2023-10-25T09:51:46 Z vnm06 Spring cleaning (CEOI20_cleaning) C++14
37 / 100
 1000 ms 32856 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 101 ms 20628 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 19288 KB Output is correct
2 Correct 32 ms 19512 KB Output is correct
3 Correct 22 ms 24272 KB Output is correct
4 Correct 43 ms 24272 KB Output is correct
5 Correct 44 ms 25544 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 20052 KB Output is correct
2 Correct 63 ms 20032 KB Output is correct
3 Correct 38 ms 32856 KB Output is correct
4 Correct 135 ms 32600 KB Output is correct
5 Correct 33 ms 30928 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 21008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 25424 KB Output is correct
2 Correct 180 ms 23380 KB Output is correct
3 Correct 155 ms 21332 KB Output is correct
4 Correct 181 ms 23292 KB Output is correct
5 Correct 182 ms 23396 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 27984 KB Output is correct
2 Execution timed out 1058 ms 29020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 101 ms 20628 KB Output is correct
3 Correct 32 ms 19288 KB Output is correct
4 Correct 32 ms 19512 KB Output is correct
5 Correct 22 ms 24272 KB Output is correct
6 Correct 43 ms 24272 KB Output is correct
7 Correct 44 ms 25544 KB Output is correct
8 Correct 60 ms 20052 KB Output is correct
9 Correct 63 ms 20032 KB Output is correct
10 Correct 38 ms 32856 KB Output is correct
11 Correct 135 ms 32600 KB Output is correct
12 Correct 33 ms 30928 KB Output is correct
13 Execution timed out 1065 ms 21008 KB Time limit exceeded
14 Halted 0 ms 0 KB -