oj.uz

Submission #961666

# Submission time Handle Problem Language Result Execution time Memory
961666 2024-04-12T09:54:52 Z Huseyn123 Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 221 ms 70884 KB 
#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

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

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45812 KB Output is correct
2 Correct 113 ms 50424 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 48292 KB Output is correct
2 Correct 87 ms 48264 KB Output is correct
3 Correct 44 ms 63100 KB Output is correct
4 Correct 125 ms 61132 KB Output is correct
5 Correct 127 ms 65732 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 49012 KB Output is correct
2 Correct 65 ms 48988 KB Output is correct
3 Correct 54 ms 69968 KB Output is correct
4 Correct 158 ms 69172 KB Output is correct
5 Correct 41 ms 66644 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 51096 KB Output is correct
2 Correct 54 ms 50924 KB Output is correct
3 Correct 16 ms 50432 KB Output is correct
4 Correct 18 ms 50780 KB Output is correct
5 Correct 18 ms 51292 KB Output is correct
6 Correct 66 ms 51084 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 56916 KB Output is correct
2 Correct 215 ms 57068 KB Output is correct
3 Correct 170 ms 51288 KB Output is correct
4 Correct 221 ms 56988 KB Output is correct
5 Correct 213 ms 56960 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 63192 KB Output is correct
2 Correct 126 ms 68484 KB Output is correct
3 Correct 166 ms 66988 KB Output is correct
4 Correct 162 ms 68176 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45812 KB Output is correct
2 Correct 113 ms 50424 KB Output is correct
3 Correct 79 ms 48292 KB Output is correct
4 Correct 87 ms 48264 KB Output is correct
5 Correct 44 ms 63100 KB Output is correct
6 Correct 125 ms 61132 KB Output is correct
7 Correct 127 ms 65732 KB Output is correct
8 Correct 70 ms 49012 KB Output is correct
9 Correct 65 ms 48988 KB Output is correct
10 Correct 54 ms 69968 KB Output is correct
11 Correct 158 ms 69172 KB Output is correct
12 Correct 41 ms 66644 KB Output is correct
13 Correct 87 ms 51096 KB Output is correct
14 Correct 54 ms 50924 KB Output is correct
15 Correct 16 ms 50432 KB Output is correct
16 Correct 18 ms 50780 KB Output is correct
17 Correct 18 ms 51292 KB Output is correct
18 Correct 66 ms 51084 KB Output is correct
19 Correct 127 ms 56916 KB Output is correct
20 Correct 215 ms 57068 KB Output is correct
21 Correct 170 ms 51288 KB Output is correct
22 Correct 221 ms 56988 KB Output is correct
23 Correct 213 ms 56960 KB Output is correct
24 Correct 192 ms 63192 KB Output is correct
25 Correct 126 ms 68484 KB Output is correct
26 Correct 166 ms 66988 KB Output is correct
27 Correct 162 ms 68176 KB Output is correct
28 Correct 169 ms 57424 KB Output is correct
29 Correct 152 ms 67736 KB Output is correct
30 Correct 119 ms 67140 KB Output is correct
31 Correct 157 ms 70884 KB Output is correct
32 Correct 207 ms 58112 KB Output is correct
33 Correct 153 ms 63248 KB Output is correct
34 Correct 163 ms 67700 KB Output is correct
35 Correct 161 ms 67408 KB Output is correct