Submission #961666

#	Time	Username	Problem	Language	Result	Execution time	Memory
961666		Huseyn123	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	221 ms	70884 KiB

cleaning

#include <bits/stdc++.h>
#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second 
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << endl;\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << (int)x << " ";\
    }\
    cout << endl;\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],c[MAX],sub[MAX],e[MAX],tp[MAX],dep[MAX],tim,pre[MAX],e1[MAX];
ll res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//int e[1001][1001];
//bool e1[1001][1001]; 
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> g;
void dfs(int v,int prev){
    pre[v]=prev;
    sub[v]=1;
    c[v]=(g[v].size()==1);
    for(auto x:g[v]){
        if(x==prev){
            continue;
        }
        dep[x]=dep[v]+1;
        dfs(x,v);
        c[v]+=c[x];
        sub[v]+=sub[x];
    }
}
void dfs_hld(int v,int prev,int top){
    int mx,ind_mx;
    mx=-INF;
    ind_mx=-1;
    tp[v]=top;
    e[v]=tim++;
    for(auto x:g[v]){
        if(x==prev){
            continue;
        }
        if(sub[x]>mx){
            mx=sub[x];
            ind_mx=x;
        }
    }
    if(ind_mx==-1){
        return;
    }
    dfs_hld(ind_mx,v,top);
    for(auto x:g[v]){
        if(x==prev || x==ind_mx){
            continue;
        }
        dfs_hld(x,v,x);
    }
}
struct segtree{
    vector<int> sums;
    vector<int> lazy;
    int sz=0;
    void init(int n){
        sz=1;
        while(sz<n){
            sz*=2;
        }
        sums.resize(2*sz,0);
        lazy.resize(2*sz,0);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                sums[x]=a[lx];
            }
            return;
        }
        int mid=(lx+rx)/2; 
        build(2*x+1,lx,mid,a);
        build(2*x+2,mid,rx,a);
        sums[x]=sums[2*x+1]+sums[2*x+2];
    }
    void build(vector<int> &a){
        build(0,0,sz,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1 || !lazy[x]){
            return;
        }
        int mid=(lx+rx)/2;
        sums[2*x+1]=mid-lx-sums[2*x+1];
        sums[2*x+2]=rx-mid-sums[2*x+2];
        lazy[2*x+1]^=1;
        lazy[2*x+2]^=1;
        lazy[x]=0;
    }
    void upd(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(lx>=r || rx<=l){
            return;
        }
        if(lx>=l && rx<=r){
            sums[x]=rx-lx-sums[x];
            lazy[x]^=1;
            return;
        }
        int mid=(lx+rx)/2;
        upd(2*x+1,lx,mid,l,r);
        upd(2*x+2,mid,rx,l,r);
        sums[x]=sums[2*x+1]+sums[2*x+2];
    }
    void upd(int l,int r){
        if(l==n || l==r){
            return;
        }
        upd(0,0,sz,l,r);
    }
    int get_sum(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(lx>=r || rx<=l){
            return 0;
        }
        if(lx>=l && rx<=r){
            return sums[x];
        }
        int mid=(lx+rx)/2;
        int s1=get_sum(2*x+1,lx,mid,l,r);
        int s2=get_sum(2*x+2,mid,rx,l,r);
        return s1+s2;
    }
    int get_sum(int l,int r){
        return get_sum(0,0,sz,l,r);
    }
};
segtree st;
void upd(int x){
    while(tp[x]!=1){
        st.upd(e[tp[x]],e[x]+1);
        //cout << e[tp[x]] << " " << e[x] << "\n";
        x=pre[tp[x]];
    }
    st.upd(e[1],e[x]+1);
    //cout << e[1] << " " << e[x] << "z\n";
}
void solve(){
    cin >> n >> q;
    g.clear();
    g.resize(n+1);
    for(int i=0;i<n-1;i++){
        cin >> x >> y; 
        g[x].pb(y);
        g[y].pb(x);
    }
    tim=0; 
    dfs(1,1);
    dfs_hld(1,1,1);
    vector<int> d(n);
    for(int i=1;i<=n;i++){
        d[e[i]]=1-c[i]%2;
        //cout << i << " " << e[i] << "\n";
    }
    //outputvec(d);
    set<int> f;
    st.init(n);
    st.build(d);
    for(int i=0;i<q;i++){
        cin >> m; 
        f.clear();
        int cnt=0;
        for(int j=0;j<m;j++){
            cin >> e1[j];
            x=e1[j];
            if((int)g[x].size()!=1 || f.find(x)!=f.end()){
                upd(x); 
            }
            else{
                cnt++;
            }
            f.ins(x);
        }
        if(st.get_sum(0,1)==0){
            cout << -1 << "\n";
        }
        else{
            cout << st.get_sum(0,n)+n+m-2 << "\n";
        }
        f.clear();
        for(int j=0;j<m;j++){
            x=e1[j];
            if((int)g[x].size()!=1 || f.find(x)!=f.end()){
                upd(x);
            }
            f.ins(x);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input13.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:240:8: warning: unused variable 'cnt1' [-Wunused-variable]
  240 |     ll cnt1=1;
      |        ^~~~

• 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