oj.uz

Submission #866041

# Submission time Handle Problem Language Result Execution time Memory
866041 2023-10-25T10:30:23 Z vnm06 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 185 ms 31780 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]); j--;}
            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], brskok=0;
            while(tekchain!=1)
            {
                brskok++;
                if(brskok>200)
                {
                    cout<<n/(max(n, n)-min(n, n))<<endl;
                }
                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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 94 ms 20132 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19032 KB Output is correct
2 Correct 31 ms 19032 KB Output is correct
3 Correct 22 ms 23548 KB Output is correct
4 Correct 41 ms 23252 KB Output is correct
5 Correct 52 ms 24456 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19548 KB Output is correct
2 Correct 67 ms 19548 KB Output is correct
3 Correct 41 ms 31780 KB Output is correct
4 Correct 121 ms 30932 KB Output is correct
5 Correct 40 ms 29796 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20824 KB Output is correct
2 Correct 34 ms 20056 KB Output is correct
3 Correct 10 ms 20060 KB Output is correct
4 Correct 11 ms 20476 KB Output is correct
5 Correct 12 ms 20828 KB Output is correct
6 Correct 50 ms 20612 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 24288 KB Output is correct
2 Correct 178 ms 22036 KB Output is correct
3 Correct 149 ms 20748 KB Output is correct
4 Correct 183 ms 22308 KB Output is correct
5 Correct 181 ms 22048 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 26272 KB Output is correct
2 Correct 91 ms 28068 KB Output is correct
3 Correct 143 ms 28896 KB Output is correct
4 Correct 124 ms 28352 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 94 ms 20132 KB Output is correct
3 Correct 31 ms 19032 KB Output is correct
4 Correct 31 ms 19032 KB Output is correct
5 Correct 22 ms 23548 KB Output is correct
6 Correct 41 ms 23252 KB Output is correct
7 Correct 52 ms 24456 KB Output is correct
8 Correct 61 ms 19548 KB Output is correct
9 Correct 67 ms 19548 KB Output is correct
10 Correct 41 ms 31780 KB Output is correct
11 Correct 121 ms 30932 KB Output is correct
12 Correct 40 ms 29796 KB Output is correct
13 Correct 71 ms 20824 KB Output is correct
14 Correct 34 ms 20056 KB Output is correct
15 Correct 10 ms 20060 KB Output is correct
16 Correct 11 ms 20476 KB Output is correct
17 Correct 12 ms 20828 KB Output is correct
18 Correct 50 ms 20612 KB Output is correct
19 Correct 137 ms 24288 KB Output is correct
20 Correct 178 ms 22036 KB Output is correct
21 Correct 149 ms 20748 KB Output is correct
22 Correct 183 ms 22308 KB Output is correct
23 Correct 181 ms 22048 KB Output is correct
24 Correct 181 ms 26272 KB Output is correct
25 Correct 91 ms 28068 KB Output is correct
26 Correct 143 ms 28896 KB Output is correct
27 Correct 124 ms 28352 KB Output is correct
28 Correct 131 ms 21844 KB Output is correct
29 Correct 133 ms 27428 KB Output is correct
30 Correct 45 ms 25932 KB Output is correct
31 Correct 144 ms 30820 KB Output is correct
32 Correct 185 ms 22044 KB Output is correct
33 Correct 131 ms 26192 KB Output is correct
34 Correct 137 ms 28716 KB Output is correct
35 Correct 162 ms 27352 KB Output is correct