| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 342500 | 2021-01-02T09:18:53 Z | urd05 | Spring cleaning (CEOI20_cleaning) | C++14 | 1000 ms | 13548 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 x;
scanf("%d",&x);
x--;
if (son[x].empty()^(getleaf(r)%2==0)) {
printf("-1\n");
continue;
}
if (son[x].empty()) {
printf("%d\n",n+ori);
}
else {
printf("%d\n",n+ori+ans(x));
}
continue;
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 5612 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 5612 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 6 ms | 6380 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 21 ms | 7660 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1081 ms | 10728 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1085 ms | 13548 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 5612 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |