oj.uz

Submission #342767

# Submission time Handle Problem Language Result Execution time Memory
342767 2021-01-02T17:55:51 Z urd05 Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 323 ms 26080 KB 
#include <bits/stdc++.h>
using namespace std;

const int s=131072;
int seg[s*2];
int lazy[s*2];

void propagate(int node,int nodel,int noder) {
    if (lazy[node]) {
        seg[node]=noder-nodel+1-seg[node];
        if (node<s) {
            lazy[node*2]^=1;
            lazy[node*2+1]^=1;
        }
        lazy[node]=0;
    }
}

int sum(int l,int r,int node=1,int nodel=0,int noder=s-1) {
    propagate(node,nodel,noder);
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int l,int r,int node=1,int nodel=0,int noder=s-1) {
    propagate(node,nodel,noder);
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        lazy[node]^=1;
        propagate(node,nodel,noder);
        return;
    }
    int mid=(nodel+noder)/2;
    update(l,r,node*2,nodel,mid);
    update(l,r,node*2+1,mid+1,noder);
    seg[node]=seg[node*2]+seg[node*2+1];
}
 
int deg[100000];
vector<int> adj[100000];
vector<int> son[100000];
int leaf[100000];
int p[100000];
int ind[100000];
int f=0;
int sz[100000];
int rev[100000];
int cnt[100000];
int top[100000];
 
void dfs(int v,int prev) {
    p[v]=prev;
    sz[v]=1;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (prev==nt) {
            continue;
        }
        son[v].push_back(nt);
        dfs(nt,v);
        sz[v]+=sz[nt];
        if (sz[son[v][0]]<sz[nt]) {
            swap(son[v][0],son[v][son[v].size()-1]);
        }
    }
}

void dfs_hld(int v) {
    ind[v]=f++;
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        top[nt]=(i==0?top[v]:nt);
        dfs_hld(nt);
    }
}

int main(void) {
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        deg[u]++;
        deg[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int r=0;
    for(int i=0;i<n;i++) {
        if (deg[i]!=1) {
            r=i;
            break;
        }
    }
    dfs(r,-1);
    top[r]=r;
    dfs_hld(r);
    for(int i=0;i<n;i++) {
        rev[ind[i]]=i;
    }
    for(int i=n-1;i>=0;i--) {
        if (son[rev[i]].empty()) {
            leaf[rev[i]]=1;
            continue;
        }
        leaf[rev[i]]=0;
        for(int j=0;j<son[rev[i]].size();j++) {
            leaf[rev[i]]+=leaf[son[rev[i]][j]];
        }
    }
    for(int i=1;i<n;i++) {
        seg[ind[i]+s]=(leaf[i]%2==0?1:0);
    }
    for(int i=s-1;i>0;i--) {
        seg[i]=seg[i*2]+seg[i*2+1];
    }
    for(int i=0;i<q;i++) {
        int k;
        vector<int> save0;
        scanf("%d",&k);
        int ret=n-1+k;
        vector<int> save;
        int l=leaf[r];
        for(int j=0;j<k;j++) {
            int v;
            scanf("%d",&v);
            v--;
            save0.push_back(v);
            if (!son[v].empty()||cnt[v]>0) {
                save.push_back(v);
                l++;
            }
            cnt[v]++;
        }
        if (l%2!=0) {
            printf("-1\n");
            for(int j=0;j<save0.size();j++) {
                cnt[save0[j]]--;
            }
            continue;
        }
        for(int j=0;j<save.size();j++) {
            int now=save[j];
            while (now!=-1) {
                update(ind[top[now]],ind[now]);
                now=p[top[now]];
            }
        }
        printf("%d\n",ret+sum(1,n-1));
        for(int j=0;j<save.size();j++) {
            int now=save[j];
            while (now!=-1) {
                update(ind[top[now]],ind[now]);
                now=p[top[now]];
            }
        }
        for(int j=0;j<save0.size();j++) {
            cnt[save0[j]]--;
        }
    }
}

Compilation message

cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs_hld(int)':
cleaning.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j=0;j<son[rev[i]].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:147:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             for(int j=0;j<save0.size();j++) {
      |                         ~^~~~~~~~~~~~~
cleaning.cpp:152:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for(int j=0;j<save0.size();j++) {
      |                     ~^~~~~~~~~~~~~
cleaning.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:136:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |             scanf("%d",&v);
      |             ~~~~~^~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5612 KB Output is correct
2 Correct 153 ms 7540 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 6760 KB Output is correct
2 Correct 16 ms 6760 KB Output is correct
3 Correct 43 ms 13416 KB Output is correct
4 Correct 88 ms 11876 KB Output is correct
5 Correct 97 ms 14312 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7528 KB Output is correct
2 Correct 17 ms 7528 KB Output is correct
3 Correct 74 ms 25324 KB Output is correct
4 Correct 172 ms 24556 KB Output is correct
5 Correct 66 ms 23228 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8300 KB Output is correct
2 Correct 56 ms 7788 KB Output is correct
3 Correct 16 ms 7404 KB Output is correct
4 Correct 16 ms 8300 KB Output is correct
5 Correct 20 ms 8428 KB Output is correct
6 Correct 73 ms 8684 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 11244 KB Output is correct
2 Correct 315 ms 11756 KB Output is correct
3 Correct 257 ms 9580 KB Output is correct
4 Correct 314 ms 12908 KB Output is correct
5 Correct 323 ms 12900 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 15212 KB Output is correct
2 Correct 140 ms 19564 KB Output is correct
3 Correct 268 ms 21228 KB Output is correct
4 Correct 148 ms 19820 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5612 KB Output is correct
2 Correct 153 ms 7540 KB Output is correct
3 Correct 93 ms 6760 KB Output is correct
4 Correct 16 ms 6760 KB Output is correct
5 Correct 43 ms 13416 KB Output is correct
6 Correct 88 ms 11876 KB Output is correct
7 Correct 97 ms 14312 KB Output is correct
8 Correct 72 ms 7528 KB Output is correct
9 Correct 17 ms 7528 KB Output is correct
10 Correct 74 ms 25324 KB Output is correct
11 Correct 172 ms 24556 KB Output is correct
12 Correct 66 ms 23228 KB Output is correct
13 Correct 107 ms 8300 KB Output is correct
14 Correct 56 ms 7788 KB Output is correct
15 Correct 16 ms 7404 KB Output is correct
16 Correct 16 ms 8300 KB Output is correct
17 Correct 20 ms 8428 KB Output is correct
18 Correct 73 ms 8684 KB Output is correct
19 Correct 88 ms 11244 KB Output is correct
20 Correct 315 ms 11756 KB Output is correct
21 Correct 257 ms 9580 KB Output is correct
22 Correct 314 ms 12908 KB Output is correct
23 Correct 323 ms 12900 KB Output is correct
24 Correct 300 ms 15212 KB Output is correct
25 Correct 140 ms 19564 KB Output is correct
26 Correct 268 ms 21228 KB Output is correct
27 Correct 148 ms 19820 KB Output is correct
28 Correct 218 ms 12396 KB Output is correct
29 Correct 229 ms 20024 KB Output is correct
30 Correct 59 ms 15080 KB Output is correct
31 Correct 167 ms 26080 KB Output is correct
32 Correct 307 ms 12780 KB Output is correct
33 Correct 207 ms 18028 KB Output is correct
34 Correct 233 ms 21100 KB Output is correct
35 Correct 237 ms 20972 KB Output is correct