oj.uz

Submission #342512

# Submission time Handle Problem Language Result Execution time Memory
342512 2021-01-02T09:55:08 Z urd05 Spring cleaning (CEOI20_cleaning) C++14
28 / 100
 1000 ms 23808 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;
    for(int i=0;i<n;i++) {
        if (son[i].empty()) {
            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+ori;
        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 (p[now]!=-1) {
                if (leaf[now]%2==0) {
                    ret--;
                }
                else {
                    ret++;
                }
                leaf[now]++;
                now=p[now];
            }
        }
        printf("%d\n",ret);
        for(int j=0;j<save.size();j++) {
            int now=save[j];
            while (p[now]!=-1) {
                leaf[now]--;
                now=p[now];
            }
        }
        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:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int j=0;j<son[rev[i]].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:152:26: 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<save0.size();j++) {
      |                         ~^~~~~~~~~~~~~
cleaning.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         for(int j=0;j<save.size();j++) {
      |                     ~^~~~~~~~~~~~
cleaning.cpp:171:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         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:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
cleaning.cpp:141:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |             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 41 ms 7276 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6756 KB Output is correct
2 Correct 16 ms 6756 KB Output is correct
3 Correct 48 ms 13032 KB Output is correct
4 Correct 49 ms 11492 KB Output is correct
5 Correct 62 ms 13672 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 7400 KB Output is correct
2 Correct 17 ms 7400 KB Output is correct
3 Correct 555 ms 23808 KB Output is correct
4 Execution timed out 1090 ms 23016 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11116 KB Output is correct
2 Correct 87 ms 10988 KB Output is correct
3 Correct 53 ms 8172 KB Output is correct
4 Correct 90 ms 10988 KB Output is correct
5 Correct 82 ms 10988 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14444 KB Output is correct
2 Correct 137 ms 17732 KB Output is correct
3 Execution timed out 1052 ms 17132 KB Time limit exceeded
4 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 41 ms 7276 KB Output is correct
3 Correct 16 ms 6756 KB Output is correct
4 Correct 16 ms 6756 KB Output is correct
5 Correct 48 ms 13032 KB Output is correct
6 Correct 49 ms 11492 KB Output is correct
7 Correct 62 ms 13672 KB Output is correct
8 Correct 990 ms 7400 KB Output is correct
9 Correct 17 ms 7400 KB Output is correct
10 Correct 555 ms 23808 KB Output is correct
11 Execution timed out 1090 ms 23016 KB Time limit exceeded
12 Halted 0 ms 0 KB -