oj.uz

Submission #1093471

# Submission time Handle Problem Language Result Execution time Memory
1093471 2024-09-27T00:35:54 Z Lemser Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 177 ms 29524 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
 
#define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;}
bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;}
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
ll gauss(ll n){return (n*(n+1))/2;}
const int N = 2e5 + 7, LOG=20;
vi graph[N];
int ni[N],szl[N],szn[N],tin[N],tout[N],heavy[N],pa[N],anc[N],cn[N];
int timer,ans,r,n,q,k,h;
struct SegTree{
    SegTree *left,*right;
    int l,r,c,lz;
    SegTree(){}
    SegTree(int l,int r):l(l),r(r),c(0),lz(0),left(nullptr),right(nullptr){
        if(l==r)return;
        int m=(l+r)/2;
        left=new SegTree(l, m);
        right=new SegTree(m+1,r);
    }
    void push(){
        if(lz)c=r-l+1-c;
        if(l!=r){
            left->lz^=lz;
            right->lz^=lz;
        }
        lz=0;
    }
    void update(int i,int j){
        push();
        if(l>j||r<i)return;
        if(l>=i&&r<=j){
            lz^=1;
            push();
            return;
        }
        left->update(i,j);
        right->update(i,j);
        c=left->c+right->c;
    }
};
SegTree *root;
void dfs(int u,int p=0){
    szl[u]=(sz(graph[u])==1);
    h+=(sz(graph[u])==1);
    szn[u]=1;
    for(int v:graph[u]){
        if(v==p)continue;
        ni[v]=ni[u]+1;
        pa[v]=u;
        dfs(v, u);
        szl[u]+=szl[v];
        szn[u]+=szn[v];
    }
    for(int v:graph[u]){
        if(v!=p&&szn[heavy[u]]<szn[v]){
            heavy[u]=v;
        }
    }
}
void dfs1(int u,int p,int anct){
    tin[u]=timer++;
    if(sz(graph[u])>1)dfs1(heavy[u], u, anct);
    anc[u]=anct;
    if(szl[u]&1)root->update(tin[u],tin[u]);
    for(int v:graph[u]){
        if(v==p||v==heavy[u])continue;
        dfs1(v, u, v);
    }
}
void update(int u){
    while(u != 0){
        root->update(tin[anc[u]], tin[u]);
        u=pa[anc[u]];
    }
}
void test_case(){
    cin>>n>>q;
    fo(i,n-1){
        int a,b;
        cin>>a>>b;
        cn[a]++;
        cn[b]++;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    fore(i,1,n+1)if(sz(graph[i])>1)r=i;
    root=new SegTree(0, n-1);
    dfs(r);
    dfs1(r, 0, r);
    while(q--){
        cin>>k;
        vi u(k);
        fo(i,k)cin>>u[i];
        int ans=0;
        fo(i,k){
            cn[u[i]]++;
            if(cn[u[i]]==2)continue;
            h++;
            update(u[i]);
        }
        root->push();
        ans=2*n+k-2-root->c;
        if(h&1)cout<<-1<<endl;
        else cout<<ans<<endl;
        fo(i,k){
            cn[u[i]]--;
            if(cn[u[i]]==1)continue;
            h--;
            update(u[i]);
        }
    }
}
int main(){cin.tie(0)->sync_with_stdio(0);
    int t=1;
    // cin >> t;
    while(t--)test_case();
}

Compilation message

cleaning.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
cleaning.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
cleaning.cpp: In constructor 'SegTree::SegTree(int, int)':
cleaning.cpp:46:15: warning: 'SegTree::lz' will be initialized after [-Wreorder]
   46 |     int l,r,c,lz;
      |               ^~
cleaning.cpp:45:14: warning:   'SegTree* SegTree::left' [-Wreorder]
   45 |     SegTree *left,*right;
      |              ^~~~
cleaning.cpp:48:5: warning:   when initialized here [-Wreorder]
   48 |     SegTree(int l,int r):l(l),r(r),c(0),lz(0),left(nullptr),right(nullptr){
      |     ^~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4968 KB Output is correct
2 Correct 79 ms 8872 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6248 KB Output is correct
2 Correct 39 ms 6248 KB Output is correct
3 Correct 46 ms 21452 KB Output is correct
4 Correct 66 ms 17408 KB Output is correct
5 Correct 75 ms 22384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7004 KB Output is correct
2 Correct 35 ms 7004 KB Output is correct
3 Correct 62 ms 29524 KB Output is correct
4 Correct 108 ms 28180 KB Output is correct
5 Correct 50 ms 27220 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9304 KB Output is correct
2 Correct 40 ms 8540 KB Output is correct
3 Correct 12 ms 8536 KB Output is correct
4 Correct 11 ms 9052 KB Output is correct
5 Correct 13 ms 9048 KB Output is correct
6 Correct 42 ms 9308 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 16980 KB Output is correct
2 Correct 165 ms 16720 KB Output is correct
3 Correct 132 ms 11344 KB Output is correct
4 Correct 173 ms 16720 KB Output is correct
5 Correct 171 ms 16720 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 23364 KB Output is correct
2 Correct 84 ms 26196 KB Output is correct
3 Correct 119 ms 25392 KB Output is correct
4 Correct 108 ms 25832 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4968 KB Output is correct
2 Correct 79 ms 8872 KB Output is correct
3 Correct 37 ms 6248 KB Output is correct
4 Correct 39 ms 6248 KB Output is correct
5 Correct 46 ms 21452 KB Output is correct
6 Correct 66 ms 17408 KB Output is correct
7 Correct 75 ms 22384 KB Output is correct
8 Correct 36 ms 7004 KB Output is correct
9 Correct 35 ms 7004 KB Output is correct
10 Correct 62 ms 29524 KB Output is correct
11 Correct 108 ms 28180 KB Output is correct
12 Correct 50 ms 27220 KB Output is correct
13 Correct 67 ms 9304 KB Output is correct
14 Correct 40 ms 8540 KB Output is correct
15 Correct 12 ms 8536 KB Output is correct
16 Correct 11 ms 9052 KB Output is correct
17 Correct 13 ms 9048 KB Output is correct
18 Correct 42 ms 9308 KB Output is correct
19 Correct 102 ms 16980 KB Output is correct
20 Correct 165 ms 16720 KB Output is correct
21 Correct 132 ms 11344 KB Output is correct
22 Correct 173 ms 16720 KB Output is correct
23 Correct 171 ms 16720 KB Output is correct
24 Correct 177 ms 23364 KB Output is correct
25 Correct 84 ms 26196 KB Output is correct
26 Correct 119 ms 25392 KB Output is correct
27 Correct 108 ms 25832 KB Output is correct
28 Correct 121 ms 15696 KB Output is correct
29 Correct 142 ms 24916 KB Output is correct
30 Correct 68 ms 22428 KB Output is correct
31 Correct 115 ms 27988 KB Output is correct
32 Correct 171 ms 16588 KB Output is correct
33 Correct 110 ms 22356 KB Output is correct
34 Correct 176 ms 24656 KB Output is correct
35 Correct 128 ms 25688 KB Output is correct