oj.uz

Submission #342510

# Submission time Handle Problem Language Result Execution time Memory
342510 2021-01-02T09:49:53 Z urd05 Spring cleaning (CEOI20_cleaning) C++14
34 / 100
 1000 ms 24812 KB 
#include <bits/stdc++.h>
using namespace std;
 
int deg[100000];
vector<int> adj[100000];
vector<int> son[100000];
int leaf[100000];
int p[100000];
int dp[100000];
const int nn=-1e9;
int ind[100000];
int f=0;
int sz[100000];
int rev[100000];
int cnt[100000];
int psum[100001];
 
int getleaf(int v) {
    if (leaf[v]!=-1) {
        return leaf[v];
    }
    if (son[v].empty()) {
        return leaf[v]=1;
    }
    leaf[v]=0;
    for(int i=0;i<son[v].size();i++) {
        leaf[v]+=getleaf(son[v][i]);
    }
    return leaf[v];
}
 
int ans(int v) {
    if (dp[v]!=nn) {
        return dp[v];
    }
    if (p[v]==-1) {
        return 0;
    }
    int got=ans(p[v]);
    if (getleaf(v)%2==0)
        got--;
    else
        got++;
    return dp[v]=got;
}
 
void dfs(int v,int prev) {
    p[v]=prev;
    ind[v]=f++;
    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];
    }
}
 
const int s=131072;
int seg[s*2];
 
int sum(int l,int r,int node=1,int nodel=0,int noder=s-1) {
    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 i,int val) {
    i+=s;
    seg[i]+=val;
    while (i>1) {
        i/=2;
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}
 
bool comp(int a,int b) {
    return ind[a]<ind[b];
}
 
int main(void) {
    int n,q;
    scanf("%d %d",&n,&q);
    memset(leaf,-1,sizeof(leaf));
    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++) {
        dp[i]=nn;
        p[i]=-1;
        if (deg[i]!=1) {
            r=i;
        }
    }
    dfs(r,-1);
    int ori=0;
    int l=0;
    for(int i=0;i<n;i++) {
        if (son[i].empty()) {
            l++;
            update(ind[i],1);
        }
        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]];
        }
        if (i&&leaf[rev[i]]%2==0) {
            ori++;
        }
    }
    for(int i=0;i<q;i++) {
        int k;
        vector<int> save0;
        scanf("%d",&k);
        int ret=n-1+k;
        vector<int> save;
        for(int j=0;j<k;j++) {
            int v;
            scanf("%d",&v);
            v--;
            save0.push_back(v);
            if (!son[v].empty()||cnt[v]>0) {
                update(ind[v],1);
                save.push_back(v);
                l++;
            }
            cnt[v]++;
        }
        if (l%2!=0) {
            printf("-1\n");
            for(int j=0;j<save.size();j++) {
                update(ind[save[j]],-1);
                l--;
            }
            for(int j=0;j<save0.size();j++) {
                cnt[save0[j]]--;
            }
            continue;
        }
        for(int i=0;i<n;i++) {
            psum[i+1]=psum[i]+seg[s+i];
        }
        for(int j=0;j<n;j++) {
            if (j!=r) {
                if ((psum[ind[j]+sz[j]]-psum[ind[j]])%2==0) {
                    ret++;
                }
            }
        }
        printf("%d\n",ret);
        for(int j=0;j<save.size();j++) {
            update(ind[save[j]],-1);
            l--;
        }
        for(int j=0;j<save0.size();j++) {
            cnt[save0[j]]--;
        }
    }
}

Compilation message

cleaning.cpp: In function 'int getleaf(int)':
cleaning.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs(int, int)':
cleaning.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int j=0;j<son[rev[i]].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for(int j=0;j<save.size();j++) {
      |                         ~^~~~~~~~~~~~
cleaning.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for(int j=0;j<save0.size();j++) {
      |                         ~^~~~~~~~~~~~~
cleaning.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for(int j=0;j<save0.size();j++) {
      |                     ~^~~~~~~~~~~~~
cleaning.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
cleaning.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |             scanf("%d",&v);
      |             ~~~~~^~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 311 ms 7340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6756 KB Output is correct
2 Correct 26 ms 6760 KB Output is correct
3 Correct 49 ms 13416 KB Output is correct
4 Correct 53 ms 11748 KB Output is correct
5 Correct 69 ms 14056 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7400 KB Output is correct
2 Correct 25 ms 7400 KB Output is correct
3 Correct 73 ms 24812 KB Output is correct
4 Correct 100 ms 24032 KB Output is correct
5 Correct 65 ms 22892 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7788 KB Output is correct
2 Correct 32 ms 7276 KB Output is correct
3 Correct 25 ms 7276 KB Output is correct
4 Correct 16 ms 8044 KB Output is correct
5 Correct 32 ms 7788 KB Output is correct
6 Correct 46 ms 8172 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 11512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 14444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 311 ms 7340 KB Output is correct
3 Correct 23 ms 6756 KB Output is correct
4 Correct 26 ms 6760 KB Output is correct
5 Correct 49 ms 13416 KB Output is correct
6 Correct 53 ms 11748 KB Output is correct
7 Correct 69 ms 14056 KB Output is correct
8 Correct 27 ms 7400 KB Output is correct
9 Correct 25 ms 7400 KB Output is correct
10 Correct 73 ms 24812 KB Output is correct
11 Correct 100 ms 24032 KB Output is correct
12 Correct 65 ms 22892 KB Output is correct
13 Correct 58 ms 7788 KB Output is correct
14 Correct 32 ms 7276 KB Output is correct
15 Correct 25 ms 7276 KB Output is correct
16 Correct 16 ms 8044 KB Output is correct
17 Correct 32 ms 7788 KB Output is correct
18 Correct 46 ms 8172 KB Output is correct
19 Execution timed out 1094 ms 11512 KB Time limit exceeded
20 Halted 0 ms 0 KB -