oj.uz

Submission #985334

# Submission time Handle Problem Language Result Execution time Memory
985334 2024-05-17T15:47:01 Z alexdd Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 205 ms 20304 KB 
#include<bits/stdc++.h>
using namespace std;
/*ifstream fin("input.in");
ofstream fout("output.out");
#define cin fin
#define cout fout*/
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%2==0)
        return;
    aint[nod*2].lazy++;
    aint[nod*2+1].lazy++;
    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++;
        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];
bool schimba[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];
            if(siz[aux[i]]==1 && visited[aux[i]]!=pas)
            {
                visited[aux[i]]=pas;
                schimba[i]=0;
            }
            else
            {
                auxf++;
                schimba[i]=1;
            hld_upd(aux[i]);
            }
        }
        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++)
            if(schimba[i])
                hld_upd(aux[i]);
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 77 ms 6012 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5464 KB Output is correct
2 Correct 47 ms 5976 KB Output is correct
3 Correct 39 ms 13004 KB Output is correct
4 Correct 60 ms 11984 KB Output is correct
5 Correct 67 ms 13772 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5724 KB Output is correct
2 Correct 38 ms 6232 KB Output is correct
3 Correct 48 ms 20304 KB Output is correct
4 Correct 96 ms 19856 KB Output is correct
5 Correct 42 ms 19024 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6676 KB Output is correct
2 Correct 36 ms 6632 KB Output is correct
3 Correct 10 ms 5980 KB Output is correct
4 Correct 10 ms 6492 KB Output is correct
5 Correct 11 ms 6748 KB Output is correct
6 Correct 41 ms 6952 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10320 KB Output is correct
2 Correct 156 ms 11620 KB Output is correct
3 Correct 127 ms 7504 KB Output is correct
4 Correct 205 ms 11444 KB Output is correct
5 Correct 154 ms 11368 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 12348 KB Output is correct
2 Correct 86 ms 16828 KB Output is correct
3 Correct 111 ms 16984 KB Output is correct
4 Correct 115 ms 16464 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 77 ms 6012 KB Output is correct
3 Correct 41 ms 5464 KB Output is correct
4 Correct 47 ms 5976 KB Output is correct
5 Correct 39 ms 13004 KB Output is correct
6 Correct 60 ms 11984 KB Output is correct
7 Correct 67 ms 13772 KB Output is correct
8 Correct 35 ms 5724 KB Output is correct
9 Correct 38 ms 6232 KB Output is correct
10 Correct 48 ms 20304 KB Output is correct
11 Correct 96 ms 19856 KB Output is correct
12 Correct 42 ms 19024 KB Output is correct
13 Correct 58 ms 6676 KB Output is correct
14 Correct 36 ms 6632 KB Output is correct
15 Correct 10 ms 5980 KB Output is correct
16 Correct 10 ms 6492 KB Output is correct
17 Correct 11 ms 6748 KB Output is correct
18 Correct 41 ms 6952 KB Output is correct
19 Correct 101 ms 10320 KB Output is correct
20 Correct 156 ms 11620 KB Output is correct
21 Correct 127 ms 7504 KB Output is correct
22 Correct 205 ms 11444 KB Output is correct
23 Correct 154 ms 11368 KB Output is correct
24 Correct 154 ms 12348 KB Output is correct
25 Correct 86 ms 16828 KB Output is correct
26 Correct 111 ms 16984 KB Output is correct
27 Correct 115 ms 16464 KB Output is correct
28 Correct 115 ms 11344 KB Output is correct
29 Correct 106 ms 16772 KB Output is correct
30 Correct 67 ms 13772 KB Output is correct
31 Correct 94 ms 20052 KB Output is correct
32 Correct 170 ms 11532 KB Output is correct
33 Correct 109 ms 14928 KB Output is correct
34 Correct 116 ms 16720 KB Output is correct
35 Correct 115 ms 16720 KB Output is correct