oj.uz

Submission #1023372

# Submission time Handle Problem Language Result Execution time Memory
1023372 2024-07-14T17:16:13 Z DobromirAngelov Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 97 ms 61208 KB 
#include<bits/stdc++.h>
#define endl '\n'
#define int long long

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(int i=0;i<adj[v].size();i++)
    {
        int u=adj[v][i];
        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(int i=0;i<adj[v].size();i++)
    {
        int u=adj[v][i];
        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(int i=0;i<adj[v].size();i++)
    {
        int u=adj[v][i];
        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);
    //for(auto v: virtNodes) cout<<v<<" "; cout<<endl;

    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);
    }
//cout<<st[0]<<endl;

    //for(auto v: nodes) cout<<v<<" "; cout<<endl;

    return st[0];
}

pair<int,int> dfs_virt(int v,int par)
{//cout<<v<<endl;
    int ret=0;
    int cntUsed=0;
    if(used[v]) cntUsed=1;
    for(int i=0;i<vAdj[v].size();i++)
    {
        int u=vAdj[v][i];
        //if(u==par) continue;
        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};
}

signed 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,-1).first;
            for(auto v: virtNodes) used[v]=0;
        }
        cout<<ans<<endl;
    }

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

return 0;
}
/*
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
*/

Compilation message

cleaning.cpp: In function 'void dfs(long long int, long long int, long long int)':
cleaning.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs2(long long int, long long int)':
cleaning.cpp:54:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs3(long long int, long long int)':
cleaning.cpp:68:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'std::pair<long long int, long long int> dfs_virt(long long int, long long int)':
cleaning.cpp:157:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i=0;i<vAdj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Incorrect 36 ms 22356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 7 ms 14484 KB Output is correct
3 Correct 49 ms 51424 KB Output is correct
4 Correct 47 ms 44444 KB Output is correct
5 Correct 69 ms 55496 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17244 KB Output is correct
2 Correct 9 ms 17004 KB Output is correct
3 Correct 94 ms 58788 KB Output is correct
4 Correct 97 ms 61208 KB Output is correct
5 Correct 64 ms 55592 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24668 KB Output is correct
2 Incorrect 17 ms 21848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 40784 KB Output is correct
2 Correct 67 ms 40764 KB Output is correct
3 Correct 46 ms 27476 KB Output is correct
4 Correct 72 ms 40904 KB Output is correct
5 Correct 61 ms 40784 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 52668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Incorrect 36 ms 22356 KB Output isn't correct
3 Halted 0 ms 0 KB -