Submission #1023394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023394		DobromirAngelov	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	85 ms	39036 KiB

cleaning

#pragma GCC Optimize("Ofast")

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=1e5+5;
const int MAXQ=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,int d)
{
    depth[v]=d;
    subLf[v]=0;
    if(leaf[v]) subLf[v]=1;

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

void dfs2(int v,int par)
{
    if(subLf[v]%2==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/2]+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=0;
    if(used[v]) cntUsed=1;
    for(auto u: vAdj[v])
    {
        auto cur=dfs_virt(u,v);
        ret+=cur.first;
        cntUsed+=cur.second;
    }

    if(cntUsed%2==1 && par!=-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;
}

dfs(root,-1,1);

dfs2(root,-1);

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

for(int i=1;i<=n;i++)
{
    if(i==root) continue;
    if(subLf[i]%2==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]%2==1) virtNodes.push_back(v);
    }

    if((subLf[root]+virtNodes.size())%2==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 (stderr)

cleaning.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("Ofast")
      |

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30