QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#564868 | #9295. Treeshop | ucup-team3161# | WA | 3ms | 26496kb | C++17 | 3.1kb | 2024-09-15 16:08:53 | 2024-09-15 16:08:54 |
Judging History
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'