# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
342496 | 2021-01-02T09:09:21 Z | urd05 | Spring cleaning (CEOI20_cleaning) | C++14 | 1000 ms | 23972 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 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 (i!=r) { if (getleaf(i)%2==0) { ori++; } } if (son[i].empty()) { update(ind[i],1); } } for(int i=0;i<q;i++) { int k; vector<int> cnt(n); for(int j=0;j<n;j++) { cnt[j]=0; } scanf("%d",&k); int ret=n-1+k; int l=getleaf(r); vector<int> save; for(int j=0;j<k;j++) { int v; scanf("%d",&v); 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); } continue; } for(int j=0;j<n;j++) { if (j!=r) { if (sum(ind[j],ind[j]+sz[j]-1)%2==0) { ret++; } } } printf("%d\n",ret); for(int j=0;j<save.size();j++) { update(ind[save[j]],-1); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5484 KB | Output is correct |
2 | Execution timed out | 1090 ms | 7076 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 6248 KB | Output is correct |
2 | Correct | 23 ms | 6248 KB | Output is correct |
3 | Correct | 66 ms | 12648 KB | Output is correct |
4 | Correct | 69 ms | 10852 KB | Output is correct |
5 | Correct | 92 ms | 12776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 7016 KB | Output is correct |
2 | Correct | 25 ms | 7016 KB | Output is correct |
3 | Correct | 93 ms | 23972 KB | Output is correct |
4 | Correct | 108 ms | 23152 KB | Output is correct |
5 | Correct | 90 ms | 22252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1088 ms | 7660 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1060 ms | 10772 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1090 ms | 13420 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5484 KB | Output is correct |
2 | Execution timed out | 1090 ms | 7076 KB | Time limit exceeded |