# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
342519 | 2021-01-02T10:06:49 Z | leinad2 | Spring cleaning (CEOI20_cleaning) | C++17 | 94 ms | 7916 KB |
#include<bits/stdc++.h> using namespace std; int n, i, j, k, r, q, a, b, cnt, sz[100010], p[100010], ans, sum[100010], depth[100010]; vector<int>adj[100010]; void dfs(int v, int par, int d) { sum[v]=sum[par]; p[v]=par; depth[v]=d; sz[v]=0; sum[v]=0; if(adj[v].size()==1) { sum[v]=sz[v]=1; return; } for(int i=0;i<adj[v].size();i++) { int p=adj[v][i]; if(p==par)continue; dfs(p, v, d+1); sz[v]+=sz[p]; sum[v]+=sum[p]; } sz[v]%=2; sum[v]+=sz[v]; } int main() { for(scanf("%d %d", &n, &q);++i<n;) { scanf("%d %d", &a, &b); adj[a].push_back(b); adj[b].push_back(a); } ans=n-1; for(i=0;i++<n;) { if(adj[i].size()>1) { r=i; break; } } dfs(r, 0, 1); for(i=0;i++<n;)sz[i]%=2; for(i=0;i++<n;) { if(sz[i]%2==0)ans++; } ans--; while(q--) { cnt=n; vector<int>v; scanf("%d %d", &a, &a); if(sz[r]%2==0) { if(adj[a].size()!=1) { puts("-1"); continue; } } else { if(adj[a].size()==1) { puts("-1"); continue; } } if(adj[a].size()==1)printf("%d\n", ans+1); else { printf("%d", 2*sum[a]-depth[a]+ans); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 2668 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 2796 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 3308 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 12 ms | 4332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 52 ms | 6124 KB | Output is correct |
2 | Incorrect | 38 ms | 5740 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 94 ms | 7916 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 2668 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |