QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564868#9295. Treeshopucup-team3161#WA 3ms26496kbC++173.1kb2024-09-15 16:08:532024-09-15 16:08:54

Judging History

This is the latest submission verdict.

  • [2024-09-15 16:08:54]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 26496kb
  • [2024-09-15 16:08:53]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define fi first
#define se second
const int N=2e5+5;
int n1,n2,m;
struct Tree
{
	int n,o,o1,o2,d,dep[N];vector<int> e[N];
	int h[N],h1[N],w[N],mxh[N][3],fa[N][18],mxw[N][18];
	void adde(int u,int v) {e[u].eb(v);e[v].eb(u);}
	void dfs(int u,int f)
	{
		bool fl=0;
		for(auto v:e[u]) if(v!=f)
		{
			fl=1;dfs(v,u);
			for(int i=0;i<3;++i) if(h[v]>mxh[u][i])
			{for(int j=2;j>i;--j) mxh[u][j]=mxh[u][j-1];mxh[u][i]=h[v];break;}
		}
		if(fl) h[u]=mxh[u][0]+1;
		for(auto v:e[u]) if(v!=f) w[v]=mxh[u][mxh[u][0]==h[v]]+1;
	}
	void dfs1(int u,int f)
	{
		dep[u]=dep[f]+1;fa[u][0]=f;mxw[u][0]=w[u];
		for(int i=1;i<=17;++i) fa[u][i]=fa[fa[u][i-1]][i-1],
			mxw[u][i]=max(mxw[u][i-1],mxw[fa[u][i-1]][i-1]);
		for(auto v:e[u]) if(v!=f) h1[v]=max(h1[u]+1,w[v]),dfs1(v,u);
	}
	void geto(int u,int f)
	{
		dep[u]=dep[f]+1;if(dep[u]>dep[o]) o=u;
		for(auto v:e[u]) if(v!=f) geto(v,u);
	}
	int lca(int u,int v)
	{
		if(dep[u]<dep[v]) swap(u,v);
		for(int i=17;i>=0;--i) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
		if(u==v) return u;
		for(int i=17;i>=0;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
		return fa[u][0];
	}
	int dst(int u,int v) {return dep[u]+dep[v]-dep[lca(u,v)]*2;}
	pair<int,int> get(int u,int x)
	{
		int res=0;
		while(x)
		{
			int t=__builtin_ctz(x&-x);
			res=max(res,mxw[u][t]);u=fa[u][t];x^=(1<<t);
		}
		return {u,res};
	}
	int qry(int u,int v)
	{
		if(u==v) return max(h[u],h1[u])*2;
		if(dep[u]<dep[v]) swap(u,v);int t=lca(u,v),w;
		if(v==t) return dep[u]-dep[v]+max({h[u],h1[v],get(u,dep[u]-dep[v]).se})*2;
		auto [u1,wu]=get(u,dep[u]-dep[t]-1);
		auto [v1,wv]=get(v,dep[v]-dep[t]-1);
		if(mxh[t][0]!=max(h[u1],h[v1])) w=mxh[t][0];
		else if(mxh[t][1]!=min(h[u1],h[v1])) w=mxh[t][1];else w=mxh[t][2];
		return dst(u,v)+max({w+1,wu,wv,h[u],h[v],h1[t]})*2;
	}
	void init() {geto(1,0);o1=o;o=0;geto(o1,0);o2=o;d=dep[o];dfs(1,0);dfs1(1,0);}
}TR1,TR2;
void W(int &x,int y) {x=min(x,y);}
int dv(int x,int y) {return x<1?0:(x-1)/y+1;}
void slv(int u1,int v1,int d1,int u2,int v2,int d2,Tree &TR1,Tree &TR2)
{
	if(TR1.qry(u1,v1)>=d2) {puts("2");return;}
	int res=1e9,o1=TR1.o1,o2=TR1.o2;
	W(res,dv(d2-TR1.dst(u1,o1)-TR1.qry(o1,v1),TR1.d*2)*2+3);
	W(res,dv(d2-TR1.dst(u1,o1)-TR1.dst(o1,o2)-TR1.qry(o2,v1),TR1.d*2)*2+4);
	swap(o1,o2);
	W(res,dv(d2-TR1.dst(u1,o1)-TR1.qry(o1,v1),TR1.d*2)*2+3);
	W(res,dv(d2-TR1.dst(u1,o1)-TR1.dst(o1,o2)-TR1.qry(o2,v1),TR1.d*2)*2+4);
	printf("%d\n",res);
}
int main()
{
	scanf("%d %d %d",&n1,&n2,&m);TR1.n=n1;TR2.n=n2;
	for(int i=1,u,v;i<n1;++i) scanf("%d %d",&u,&v),TR1.adde(u,v);
	for(int i=1,u,v;i<n2;++i) scanf("%d %d",&u,&v),TR2.adde(u,v);
	TR1.init();TR2.init();
	while(m--)
	{
		int u1,v1,u2,v2,d1,d2;scanf("%d %d %d %d",&u1,&u2,&v1,&v2);
		d1=TR1.dst(u1,v1);d2=TR2.dst(u2,v2);
		if(u1==v1 && u2==v2) {puts("0");continue;}
		if(d1==d2) {puts("1");continue;}
		if(n1<2 || n2<2 || (d1^d2)&1) {puts("-1");continue;}
		if(d1<d2) slv(u1,v1,d1,u2,v2,d2,TR1,TR2);
		else slv(u2,v2,d2,u1,v1,d1,TR2,TR1);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 26496kb

input:

4 5 7
1 2
2 3
2 4
1 2
2 3
3 4
4 5
1 1 2 5
1 5 4 1
1 5 4 2
2 5 2 3
2 1 2 5
3 2 3 2
4 4 1 2

output:

-1
2
-1
2
3
0
1

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 25488kb

input:

1 3 4
1 2
2 3
1 1 1 1
1 2 1 2
1 2 1 3
1 1 1 3

output:

0
0
-1
-1

result:

ok 4 number(s): "0 0 -1 -1"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 25428kb

input:

6 2 18
1 2
2 3
3 4
4 5
5 6
1 2
1 1 1 2
1 1 2 2
1 1 3 2
1 1 4 2
1 1 5 2
1 1 6 2
1 1 1 1
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 6 1
1 2 1 2
1 2 2 2
1 2 3 2
1 2 4 2
1 2 5 2
1 2 6 2

output:

-1
1
-1
2
-1
4
0
-1
2
-1
3
-1
0
-1
2
-1
3
-1

result:

wrong answer 4th numbers differ - expected: '3', found: '2'