oj.uz

Submission #1023398

# Submission time Handle Problem Language Result Execution time Memory
1023398 2024-07-14T17:39:57 Z DobromirAngelov Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 78 ms 39012 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=1e5+5;
const int MAXLOG=21;

int n,q;
vector<int> adj[MAXN];

bool leaf[MAXN];
int root=1;
int subLf[MAXN];
int depth[MAXN];
int cnt1[MAXN], cnt2[MAXN];
int ansOrg=0;

int tin[MAXN];
int order[2*MAXN];
int timer=0;

int lg2[2*MAXN];
int spT[2*MAXN][MAXLOG];

unordered_set<int> s;
int newCnt[MAXN];
vector<int> virtNodes;
vector<int> vAdj[MAXN];
int used[MAXN];

void dfs(int v,int par)
{
    subLf[v]=0;
    if(leaf[v]) subLf[v]=1;

    for(auto u: adj[v])
    {
        if(u==par) continue;
        depth[u]=depth[v]+1;
        dfs(u,v);
        subLf[v]+=subLf[u];
    }
}

void dfs2(int v,int par)
{
    if(subLf[v]&1==1) cnt1[v]++;
    else cnt2[v]++;

    for(auto u: adj[v])
    {
        if(u==par) continue;
        cnt1[u]=cnt1[v];
        cnt2[u]=cnt2[v];
        dfs2(u,v);
    }
}

void dfs3(int v,int par)
{
    order[++timer]=v;
    tin[v]=timer;
    for(auto u: adj[v])
    {
        if(u==par) continue;
        dfs3(u,v);
        order[++timer]=v;
    }
}

void sparseTable()
{
    lg2[0]=-1;
    for(int i=1;i<=timer;i++)
    {
        lg2[i]=lg2[i>>1]+1;
        spT[i][0]=order[i];
    }

    for(int j=1;(1<<j)<=timer;j++)
    {
        for(int i=1;i<=timer;i++)
        {
            if(i+(1<<(j-1))>timer) break;
            spT[i][j]=spT[i][j-1];
            if(depth[spT[i+(1<<(j-1))][j-1]]<depth[spT[i][j-1]]) spT[i][j]=spT[i+(1<<(j-1))][j-1];
        }
    }
}

int lca(int u,int v)
{
    if(tin[u]>tin[v]) swap(u,v);
    int d=tin[v]-tin[u]+1;
    int c1=spT[tin[u]][lg2[d]];
    int c2=spT[tin[v]-(1<<lg2[d])+1][lg2[d]];
    if(depth[c1]<=depth[c2]) return c1;
    return c2;
}

bool cmp(int u,int v)
{
    return tin[u]<tin[v];
}

int buildVirtTree()
{
    for(auto v: virtNodes) used[v]=1;

    sort(virtNodes.begin(), virtNodes.end(), cmp);
    int sz=virtNodes.size();
    for(int i=1;i<sz;i++)
    {
        virtNodes.push_back(lca(virtNodes[i-1], virtNodes[i]));
    }

    sort(virtNodes.begin(), virtNodes.end(), cmp);

    vector<int> nodes;
    for(auto v: virtNodes)
    {
        if(!nodes.empty() && nodes.back()!=v) nodes.push_back(v);
        if(nodes.empty()) nodes.push_back(v);
    }

    for(auto v: nodes) vAdj[v].clear();

    vector<int> st;
    for(auto v: nodes)
    {
        while(!st.empty() && lca(st.back(), v)!=st.back()) st.pop_back();
        if(!st.empty())
        {
            vAdj[st.back()].push_back(v);
        }
        st.push_back(v);
    }

    return st[0];
}

pair<int,int> dfs_virt(int v,int par)
{
    int ret=0;
    int cntUsed=used[v];
    for(auto u: vAdj[v])
    {
        auto cur=dfs_virt(u,v);
        ret+=cur.first;
        cntUsed+=cur.second;
    }

    if(cntUsed&1==1)
    {
        int cntOdd=cnt1[v]-cnt1[par];
        int cntEv=cnt2[v]-cnt2[par];
        ret+=cntOdd-cntEv;
    }

    return {ret, cntUsed};
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>q;
for(int i=1;i<n;i++)
{
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

for(int i=1;i<=n;i++)
{
    if(adj[i].size()==1) leaf[i]=1;
    else root=i;
}

depth[root]=1;
dfs(root,-1);

dfs2(root,-1);

dfs3(root,-1);
sparseTable();

for(int i=1;i<=n;i++)
{
    if(i==root) continue;
    if(subLf[i]&1==1) ansOrg+=1;
    else ansOrg+=2;
}

for(int tt=0;tt<q;tt++)
{
    int d;
    cin>>d;
    for(int i=0;i<d;i++)
    {
        int v;
        cin>>v;
        newCnt[v]++;
        s.insert(v);
    }

    int ans=ansOrg+d;

    for(auto v: s)
    {
        if(leaf[v]) newCnt[v]--;
        if(newCnt[v]&1==1) virtNodes.push_back(v);
    }

    if((subLf[root]+virtNodes.size())&1==1) cout<<-1<<endl;
    else
    {
        if(virtNodes.size()>0)
        {
            int virtRoot=buildVirtTree();
            ans+=dfs_virt(virtRoot,root).first;
            for(auto v: virtNodes) used[v]=0;
        }
        cout<<ans<<endl;
    }

    for(auto v: s) newCnt[v]=0;
    s.clear();
    virtNodes.clear();
}

return 0;
}

Compilation message

cleaning.cpp: In function 'void dfs2(int, int)':
cleaning.cpp:48:18: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   48 |     if(subLf[v]&1==1) cnt1[v]++;
      |                 ~^~~
cleaning.cpp: In function 'std::pair<int, int> dfs_virt(int, int)':
cleaning.cpp:154:17: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  154 |     if(cntUsed&1==1)
      |                ~^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:196:18: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  196 |     if(subLf[i]&1==1) ansOrg+=1;
      |                 ~^~~
cleaning.cpp:217:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  217 |         if(newCnt[v]&1==1) virtNodes.push_back(v);
      |                      ~^~~
cleaning.cpp:220:40: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  220 |     if((subLf[root]+virtNodes.size())&1==1) cout<<-1<<endl;
      |                                       ~^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 30 ms 14884 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9560 KB Output is correct
2 Correct 6 ms 9564 KB Output is correct
3 Correct 28 ms 29392 KB Output is correct
4 Correct 39 ms 28032 KB Output is correct
5 Correct 50 ms 32372 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10328 KB Output is correct
2 Correct 8 ms 10076 KB Output is correct
3 Correct 47 ms 36692 KB Output is correct
4 Correct 70 ms 39012 KB Output is correct
5 Correct 38 ms 34644 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15192 KB Output is correct
2 Correct 16 ms 14684 KB Output is correct
3 Correct 9 ms 14428 KB Output is correct
4 Correct 9 ms 14860 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 22 ms 15452 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 22616 KB Output is correct
2 Correct 53 ms 23008 KB Output is correct
3 Correct 38 ms 17488 KB Output is correct
4 Correct 51 ms 22868 KB Output is correct
5 Correct 53 ms 22872 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 29672 KB Output is correct
2 Correct 65 ms 32336 KB Output is correct
3 Correct 72 ms 31748 KB Output is correct
4 Correct 72 ms 31952 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 30 ms 14884 KB Output is correct
3 Correct 7 ms 9560 KB Output is correct
4 Correct 6 ms 9564 KB Output is correct
5 Correct 28 ms 29392 KB Output is correct
6 Correct 39 ms 28032 KB Output is correct
7 Correct 50 ms 32372 KB Output is correct
8 Correct 8 ms 10328 KB Output is correct
9 Correct 8 ms 10076 KB Output is correct
10 Correct 47 ms 36692 KB Output is correct
11 Correct 70 ms 39012 KB Output is correct
12 Correct 38 ms 34644 KB Output is correct
13 Correct 24 ms 15192 KB Output is correct
14 Correct 16 ms 14684 KB Output is correct
15 Correct 9 ms 14428 KB Output is correct
16 Correct 9 ms 14860 KB Output is correct
17 Correct 9 ms 14940 KB Output is correct
18 Correct 22 ms 15452 KB Output is correct
19 Correct 35 ms 22616 KB Output is correct
20 Correct 53 ms 23008 KB Output is correct
21 Correct 38 ms 17488 KB Output is correct
22 Correct 51 ms 22868 KB Output is correct
23 Correct 53 ms 22872 KB Output is correct
24 Correct 69 ms 29672 KB Output is correct
25 Correct 65 ms 32336 KB Output is correct
26 Correct 72 ms 31748 KB Output is correct
27 Correct 72 ms 31952 KB Output is correct
28 Correct 49 ms 22872 KB Output is correct
29 Correct 63 ms 32220 KB Output is correct
30 Correct 45 ms 31868 KB Output is correct
31 Correct 70 ms 39008 KB Output is correct
32 Correct 53 ms 23120 KB Output is correct
33 Correct 70 ms 29524 KB Output is correct
34 Correct 77 ms 32196 KB Output is correct
35 Correct 78 ms 33292 KB Output is correct