제출 #342767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342767		urd05	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	323 ms	26080 KiB

cleaning

#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]]--;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30