QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734757#2644. Cats or DogsShumomo0 1ms7940kbC++143.6kb2024-11-11 14:56:062024-11-11 14:56:06

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 14:56:06]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：7940kb
查看
  • [2024-11-11 14:56:06]
  • 提交

answer

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
int sz[100009],mx[100009],h[100009],ver[200009],nxt[200009],tot,ff[100009],tp[100009],dfn[100009],ed[100009],n;
struct nd{
	int x[2];
}g[100009];
struct node{
	int x[4];
	node operator +(const node &aa)const{
		node cc;
		cc.x[0]=min(min(x[0]+aa.x[2],x[1]+aa.x[0])+1,min(x[0]+aa.x[0],x[1]+aa.x[2]));
		cc.x[1]=min(min(x[0]+aa.x[3],x[1]+aa.x[1])+1,min(x[0]+aa.x[1],x[1]+aa.x[3]));
		cc.x[2]=min(min(x[2]+aa.x[2],x[3]+aa.x[0])+1,min(x[2]+aa.x[0],x[3]+aa.x[2]));
		cc.x[3]=min(min(x[2]+aa.x[3],x[3]+aa.x[1])+1,min(x[2]+aa.x[1],x[3]+aa.x[3]));
		return cc;
	}
	node operator +(const nd &aa)const{
		node cc;
		cc.x[1]=cc.x[2]=1;
		cc.x[0]=x[0]+min(aa.x[1]+1,aa.x[0]);
		cc.x[3]=x[3]+min(aa.x[1],aa.x[0]+1);
		return cc;
	}
}f[100009],d[100009],val[400009];
void add(nd &cc,node aa){
	cc.x[0]+=min(min(aa.x[2],aa.x[3])+1,min(aa.x[0],aa.x[1]));
	cc.x[1]+=min(min(aa.x[2],aa.x[3]),min(aa.x[0],aa.x[1])+1);
}
void del(nd &cc,node aa){
	cc.x[0]-=min(min(aa.x[2],aa.x[3])+1,min(aa.x[0],aa.x[1]));
	cc.x[1]-=min(min(aa.x[2],aa.x[3]),min(aa.x[0],aa.x[1])+1);
}
void dfs1(int x,int fa){
	sz[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		if(ver[i]!=fa){
			dfs1(ver[i],x);
			sz[x]+=sz[ver[i]];
			if(sz[ver[i]]>sz[mx[x]])mx[x]=ver[i];
		}
	}
}
void dfs2(int x,int fa,int tt){
	tp[x]=tt;
	ed[tt]=x;
	ff[x]=fa;
	dfn[x]=++tot;
	if(mx[x])dfs2(mx[x],x,tt);
	for(int i=h[x];i;i=nxt[i]){
		if(ver[i]!=fa&&ver[i]!=mx[x]){
			dfs2(ver[i],x,ver[i]);
		}
	}
}
void build(int rt,int l,int r){
	if(l==r){
		val[rt]=f[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	val[rt]=val[rt<<1]+val[rt<<1|1];
}
void update(int rt,int l,int r,int ll,node rr){
	if(ll<l)return;
	if(l==r){
		val[rt]=rr;
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)update(rt<<1,l,mid,ll,rr);
	else update(rt<<1|1,mid+1,r,ll,rr);
	val[rt]=val[rt<<1]+val[rt<<1|1];
}
node query(int rt,int l,int r,int ll,int rr){
	if(l>rr||r<ll){
		node rtn;
		rtn.x[0]=rtn.x[3]=0;
		rtn.x[1]=rtn.x[2]=1;
		return rtn;
	}
	if(l>=ll&&r<=rr){
		return val[rt];
	}
	int mid=(l+r)>>1;
	return query(rt<<1,l,mid,ll,rr)+query(rt<<1|1,mid+1,r,ll,rr);
}
void initialize(int N,vector<int> A,vector<int> B) {
	n=N;
	for(int i=0;i<n-1;i++){
		tot++;
		nxt[tot]=h[A[i]];
		ver[tot]=B[i];
		h[A[i]]=tot;
		tot++;
		nxt[tot]=h[B[i]];
		ver[tot]=A[i];
		h[B[i]]=tot;
	}
	for(int i=1;i<=n;i++){
		f[i].x[0]=f[i].x[3]=0;
		f[i].x[1]=f[i].x[2]=1;
	}
	dfs1(1,0);
	tot=0;
	dfs2(1,0,1);
	build(1,1,n);
}

int cat(int v){
	f[v].x[0]=0;
	f[v].x[1]=f[v].x[2]=f[v].x[3]=1;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}

int dog(int v) {
	f[v].x[0]=f[v].x[1]=f[v].x[2]=1;
	f[v].x[3]=0;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}

int neighbor(int v) {
	f[v].x[0]=f[v].x[3]=0;
	f[v].x[1]=f[v].x[2]=1;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 1ms
memory: 7940kb

input:

2
2 1
75
1 2
1 1
3 1
3 2
1 1
2 2
3 1
3 2
2 2
3 2
1 1
3 1
1 2
2 1
3 2
2 2
3 2
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
2 2
3 2
3 1
2 1
1 2
3 1
1 1
3 2
3 1
1 2
3 2
2 1
3 1
1 1
1 2
3 1
3 2
2 1
1 2
3 1
2 1
3 2
2 2
3 1
2 1
3 2
2 2
3 2
2 2
3 1
3 2
1 1
3 1
2 2
1 1
3 1
1 1
3 2
2 2
3 2
3 1
2 2
2 1
3 1
2 1
3 2
1 2
3 1...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0

result:

ok 75 lines

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 7912kb

input:

9
5 3
4 9
5 4
4 1
5 7
7 6
4 8
2 3
32
2 9
2 5
1 1
2 2
1 4
1 3
3 3
2 3
3 1
2 7
3 4
1 4
3 2
3 7
1 6
3 4
2 7
2 8
3 7
3 9
3 5
1 4
3 6
2 1
1 7
3 4
3 8
1 2
3 2
3 3
3 7
1 9

output:

0
0
1
1
1
2
1
1
1
1
0
1
1
1
2
1
1
1
1
1
1
2
1
1
2
1
1
1
1
1
0
1

result:

wrong answer 5th lines differ - expected: '2', found: '1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-29 22:55:56 | 开源项目