oj.uz

Submission #1023394

# Submission time Handle Problem Language Result Execution time Memory
1023394 2024-07-14T17:36:56 Z DobromirAngelov Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 85 ms 39036 KB 
#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

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

Subtask #1
0.0 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9564 KB Output is correct
2 Correct 6 ms 9564 KB Output is correct
3 Correct 28 ms 29628 KB Output is correct
4 Correct 35 ms 27840 KB Output is correct
5 Correct 45 ms 32580 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10584 KB Output is correct
2 Correct 7 ms 10076 KB Output is correct
3 Correct 47 ms 36636 KB Output is correct
4 Correct 73 ms 39036 KB Output is correct
5 Correct 38 ms 34640 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 14 ms 14684 KB Output is correct
3 Correct 8 ms 14428 KB Output is correct
4 Correct 9 ms 14940 KB Output is correct
5 Correct 13 ms 14940 KB Output is correct
6 Correct 26 ms 15392 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 22620 KB Output is correct
2 Correct 53 ms 22872 KB Output is correct
3 Correct 39 ms 17500 KB Output is correct
4 Correct 56 ms 22876 KB Output is correct
5 Correct 52 ms 22864 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 29520 KB Output is correct
2 Correct 59 ms 32172 KB Output is correct
3 Correct 71 ms 31832 KB Output is correct
4 Correct 65 ms 32100 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9308 KB Output is correct
2 Correct 30 ms 14684 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 9564 KB Output is correct
5 Correct 28 ms 29628 KB Output is correct
6 Correct 35 ms 27840 KB Output is correct
7 Correct 45 ms 32580 KB Output is correct
8 Correct 8 ms 10584 KB Output is correct
9 Correct 7 ms 10076 KB Output is correct
10 Correct 47 ms 36636 KB Output is correct
11 Correct 73 ms 39036 KB Output is correct
12 Correct 38 ms 34640 KB Output is correct
13 Correct 24 ms 15192 KB Output is correct
14 Correct 14 ms 14684 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 13 ms 14940 KB Output is correct
18 Correct 26 ms 15392 KB Output is correct
19 Correct 37 ms 22620 KB Output is correct
20 Correct 53 ms 22872 KB Output is correct
21 Correct 39 ms 17500 KB Output is correct
22 Correct 56 ms 22876 KB Output is correct
23 Correct 52 ms 22864 KB Output is correct
24 Correct 65 ms 29520 KB Output is correct
25 Correct 59 ms 32172 KB Output is correct
26 Correct 71 ms 31832 KB Output is correct
27 Correct 65 ms 32100 KB Output is correct
28 Correct 50 ms 22876 KB Output is correct
29 Correct 68 ms 32096 KB Output is correct
30 Correct 54 ms 31872 KB Output is correct
31 Correct 72 ms 39012 KB Output is correct
32 Correct 51 ms 23120 KB Output is correct
33 Correct 71 ms 29424 KB Output is correct
34 Correct 83 ms 32336 KB Output is correct
35 Correct 85 ms 33364 KB Output is correct