QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562537 | #9295. Treeshop | zjy0001 | WA | 4ms | 79864kb | C++17 | 8.2kb | 2024-09-13 18:20:31 | 2024-09-13 18:20:32 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5,INF=1e9;
struct Tree{
int n,tim,D,cnt;
vector<int>G[N];
pair<int,int>dp[N];
int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[N];
inline void init(int _n){
n=_n;
}
inline void add(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
inline void dfs1(int u,int fa){
sz[u]=1,son[u]=0,f[u]=fa,d[u]=fa?d[fa]+1:0;
for(auto v:G[u])if(v!=fa)dfs1(v,u),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
}
inline void dfs2(int u,int fa,int tp){
top[u]=tp,rk[dL[u]=++tim]=u;
if(son[u])dfs2(son[u],u,tp);
for(auto v:G[u])if(v!=fa&&v!=son[u])dfs2(v,u,v);
dR[u]=tim;
}
inline int LCA(int x,int y){
for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
return dL[x]<dL[y]?x:y;
}
inline int dist(int x,int y){
return d[x]+d[y]-d[LCA(x,y)]*2;
}
struct{
int a[N],dq[N],df[N];
int ST[20][N];
pair<int,int>dp[N][3],tmp[6];
int n,*sz,*d,*top,*dL,*dR,*rk,*f;
vector<int>*G;
inline int LCA(int x,int y){
for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
return dL[x]<dL[y]?x:y;
}
inline int dist(int x,int y){
return d[x]+d[y]-d[LCA(x,y)]*2;
}
inline void Dp1(int u,int fa){
df[u]=-INF,dq[u]=-INF;
dp[u][0]=dp[u][1]=dp[u][2]=make_pair(-INF,0);
if(a[u])dp[u][0]=make_pair(0,u);
for(auto v:G[u])if(v!=fa){
Dp1(v,u);
if(dp[v][0].first+1>dp[u][0].first)
dp[u][2]=dp[u][1],dp[u][1]=dp[u][0],dp[u][0]=make_pair(dp[v][0].first+1,v);
else if(dp[v][0].first+1>dp[u][1].first)
dp[u][2]=dp[u][1],dp[u][1]=make_pair(dp[v][0].first+1,v);
else dp[u][2]=max(dp[u][2],make_pair(dp[v][0].first+1,v));
}
}
inline void Dp2(int u,int fa){
for(auto v:G[u])if(v!=fa)
if(dp[u][0]==make_pair(dp[v][0].first+1,v))df[v]=dp[u][1].first;
else df[v]=dp[u][0].first;
int mx=dp[u][0].first,se=dp[u][1].first;
if(a[u])dq[u]=max(dq[u],0);
if(mx<dq[u])se=mx,mx=dq[u];
else se=max(se,dq[u]);
for(auto v:G[u])if(v!=fa){
if(mx==dp[v][0].first+1)dq[v]=se+1;
else dq[v]=mx+1;
Dp2(v,u);
}
}
inline void init(){
Dp1(1,0),Dp2(1,0);
for(int i=1;i<=n;++i)ST[0][dL[i]]=df[i];
for(int j=0,jj=1;jj<=n;++j,jj*=2)
for(int i=n-jj*2+1;i>=1;--i)
ST[j+1][i]=max(ST[j][i],ST[j][i+jj]);
}
inline int qry(int l,int r){
if(l>r)return -INF;
const int t=__lg(r-l+1);
return max(ST[t][l],ST[t][r-(1<<t)+1]);
}
inline int solve(int u,int v){
if(u==v)return max(dp[u][0].first,dq[u])*2;
int bas=dist(u,v);
if(dL[u]>dL[v])swap(u,v);
if(dL[u]<=dL[v]&&dL[v]<=dR[u]){
int ans=0;
for(;d[top[v]]>=d[u]+1;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
if(d[u]+1<=d[v])ans=max(ans,qry(dL[top[v]]+d[u]-d[top[v]]+1,dL[v]));
ans=max(ans,dq[u]);
return ans*2+bas;
}
int ans=max(dp[u][0].first,dp[v][0].first),p=LCA(u,v);
for(;d[top[u]]>=d[p]+2;u=f[top[u]])ans=max(ans,qry(dL[top[u]],dL[u]));
if(d[p]+2<=d[u])ans=max(ans,qry(dL[top[u]]+d[p]-d[top[u]]+2,dL[u]));
for(;d[top[v]]>=d[p]+2;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
if(d[p]+2<=d[v])ans=max(ans,qry(dL[top[v]]+d[p]-d[top[v]]+2,dL[v]));
if(d[top[u]]>d[p]+1)u=f[top[u]];else u=rk[dL[top[u]]+d[p]-d[top[u]]+1];
if(d[top[v]]>d[p]+1)v=f[top[v]];else v=rk[dL[top[v]]+d[p]-d[top[v]]+1];
if(dp[p][0].second!=u&&dp[p][0].second!=v)ans=max(ans,dp[p][0].first);
else if(dp[p][1].second!=u&&dp[p][1].second!=v)ans=max(ans,dp[p][1].first);
else ans=max(ans,dp[p][2].first);
ans=max(ans,dq[p]);
return ans*2+bas;
}
}T,H;
inline void dfs(int u,int fa,int k){
if(G[u].size()==1)bl[u]=k;
for(auto v:G[u])if(v!=fa)dfs(v,u,k);
}
inline void Dp1(int u,int fa){
if(bl[u])dp[u].first=u;
for(auto v:G[u])if(v!=fa){
Dp1(v,u);
auto [a,b]=dp[u];auto [c,d]=dp[v];
if(c&&(!a||dist(a,u)<dist(c,u)))swap(a,c);
if(d&&(!a||dist(a,u)<dist(d,u)))swap(a,d);
if(c&&(!b||dist(b,u)<dist(c,u)))swap(b,c);
if(d&&(!b||dist(b,u)<dist(d,u)))swap(b,d);
if(d&&(!c||dist(c,u)<dist(d,u)))swap(c,d);
dp[u].first=a;
if(b&&bl[a]!=bl[b])dp[u].second=b;
else if(c&&bl[a]!=bl[c])dp[u].second=c;
else if(d&&bl[a]!=bl[d])dp[u].second=d;
}
}
inline void Dp2(int u,int fa){
for(auto v:G[u])if(v!=fa){
auto [a,b]=dp[u];auto [c,d]=dp[v];
if(c&&(!a||dist(a,v)<dist(c,v)))swap(a,c);
if(d&&(!a||dist(a,v)<dist(d,v)))swap(a,d);
if(c&&(!b||dist(b,v)<dist(c,v)))swap(b,c);
if(d&&(!b||dist(b,v)<dist(d,v)))swap(b,d);
if(d&&(!c||dist(c,v)<dist(d,v)))swap(c,d);
dp[v].first=a;
if(b&&bl[a]!=bl[b])dp[v].second=b;
else if(c&&bl[a]!=bl[c])dp[v].second=c;
else if(d&&bl[a]!=bl[d])dp[v].second=d;
Dp2(v,u);
}
}
inline void build(){
dfs1(1,0),dfs2(1,0,1);
int rtx=1,rty=1,rt=0;
for(int i=1;i<=n;++i)if(d[i]>d[rtx])rtx=i;
for(int i=1;i<=n;++i)if(dist(rtx,i)>dist(rtx,rty))rty=i;
if(d[rtx]>d[rty])swap(rtx,rty);
D=dist(rtx,rty),rt=rty;
for(int i=0;i<D/2;++i)rt=f[rt];
if(D&1)dfs(rt,f[rt],++cnt),dfs(f[rt],rt,++cnt);
else for(auto v:G[rt])dfs(v,rt,++cnt);
Dp1(1,0),Dp2(1,0);
for(int i=1;i<=n;++i)H.a[i]=1,T.a[i]=bl[i];
H.d=d,H.dL=dL,H.dR=dR,H.G=G,H.n=n,H.rk=rk,H.sz=sz,H.top=top,H.f=f;
T.d=d,T.dL=dL,T.dR=dR,T.G=G,T.n=n,T.rk=rk,T.sz=sz,T.top=top,T.f=f;
H.init(),T.init();
}
inline int solve(int u,int v,int L){
if(H.solve(u,v)>=L)return 2;
const auto [a,b]=dp[u];const auto [c,d]=dp[v];
int sa=max(dist(u,a)+H.solve(a,v),H.solve(u,c)+dist(c,v)),sb=T.solve(u,v);
return min(max(0,(L-sa+D+D-1)/(D+D)*2)+3,max(0,(L-sb+D+D-1)/(D+D)*2)+2);
}
}T1,T2;
int n,m,q;
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>q;
T1.init(n);
for(int i=1;i<n;++i){
int u,v;cin>>u>>v;
T1.add(u,v);
}
T2.init(m);
for(int i=1;i<m;++i){
int u,v;cin>>u>>v;
T2.add(u,v);
}
if(min(n,m)<2){
for(int i=1;i<=q;++i){
int u,x,v,y;cin>>u>>x>>v>>y;
if(u==v&&x==y)cout<<"0\n";
else cout<<"-1\n";
}
return 0;
}
T1.build();
T2.build();
for(int i=1;i<=q;++i){
int u,x,v,y;cin>>u>>x>>v>>y;
int duv=T1.dist(u,v),dxy=T2.dist(x,y);
if(duv==dxy)cout<<min(duv,1)<<'\n';
else if(duv%2!=dxy%2)cout<<"-1\n";
else if(duv<dxy)cout<<T1.solve(u,v,dxy)<<'\n';
else cout<<T2.solve(x,y,duv)<<'\n';
}
return 0;
}
/*
21 56 1
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
19 1 19 51
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 73728kb
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: 4ms
memory: 45068kb
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: 0
Accepted
time: 0ms
memory: 71640kb
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 3 -1 5 0 -1 2 -1 4 -1 0 -1 2 -1 4 -1
result:
ok 18 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 79812kb
input:
21 65 8 1 2 1 3 2 18 18 4 2 5 3 19 19 6 3 20 20 7 4 8 6 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 14 17 3 21 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 ...
output:
6 6 5 5 6 6 5 5
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 79864kb
input:
10 15 10 9 10 9 3 8 3 4 8 1 4 1 6 4 5 7 5 1 2 8 9 9 10 10 2 15 2 5 15 5 1 1 3 3 13 4 13 11 4 1 6 6 14 7 6 12 7 8 12 2 7 6 14 1 11 1 6 7 5 5 2 5 11 3 13 8 10 5 6 7 6 7 11 10 11 8 1 6 6 10 11 2 13 6 10 7 12
output:
2 -1 -1 -1 -1 -1 2 2 2 -1
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 40984kb
input:
1 15 10 14 2 14 15 13 15 5 13 8 5 8 4 4 7 9 7 11 9 11 3 4 6 10 13 10 1 12 8 1 6 1 7 1 6 1 12 1 2 1 12 1 3 1 8 1 8 1 10 1 12 1 2 1 4 1 5 1 12 1 10 1 3 1 3 1 12 1 9
output:
-1 -1 -1 -1 -1 -1 -1 -1 0 -1
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 4ms
memory: 40984kb
input:
1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 40980kb
input:
25 1 10 12 3 3 25 4 25 8 4 8 9 9 18 18 6 24 6 24 1 11 1 2 9 6 5 15 5 15 7 25 21 16 21 14 1 23 2 23 19 19 10 22 8 13 22 20 13 17 8 1 1 21 1 3 1 2 1 18 1 13 1 7 1 3 1 20 1 11 1 7 1 13 1 18 1 5 1 16 1 1 1 2 1 22 1 24 1 16 1
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 75800kb
input:
14 15 30 3 5 8 5 7 8 7 4 4 13 13 11 11 14 14 10 12 4 12 1 2 13 6 2 9 6 3 12 7 3 7 11 11 10 9 10 9 6 3 5 14 9 2 3 7 1 10 4 4 15 13 10 1 8 14 2 12 6 2 14 1 8 8 4 14 11 3 14 5 3 7 10 6 11 11 9 6 10 13 4 6 5 12 3 14 3 5 6 12 11 2 4 6 8 11 12 6 4 2 13 8 11 2 4 2 12 12 6 8 15 3 11 5 12 9 3 2 14 2 11 1 8 8...
output:
2 2 -1 2 -1 2 -1 2 -1 2 2 2 -1 -1 2 -1 -1 -1 2 -1 2 -1 -1 -1 2 -1 -1 2 -1 -1
result:
ok 30 numbers
Test #10:
score: 0
Accepted
time: 3ms
memory: 75864kb
input:
14 15 30 14 1 7 1 7 2 6 2 8 6 8 13 10 13 2 3 5 3 8 4 3 12 11 7 1 9 7 15 7 1 4 1 3 4 3 13 2 13 2 14 8 4 6 8 12 6 3 9 5 9 4 11 11 10 13 8 2 2 1 15 6 7 10 9 9 1 12 6 13 15 6 13 3 12 8 3 2 9 11 2 14 5 8 7 8 5 2 1 6 1 9 12 7 5 3 13 3 12 11 4 7 4 11 8 10 1 11 1 6 2 9 8 2 12 4 9 5 7 9 12 7 6 14 2 2 2 6 3 6...
output:
-1 2 2 1 -1 -1 -1 -1 -1 2 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 2 1 2 -1 -1 1 -1 -1 2 2
result:
ok 30 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 73720kb
input:
20 15 30 16 19 19 14 3 14 1 3 20 1 17 20 1 18 9 3 9 10 15 10 9 7 12 14 5 12 11 20 4 7 2 3 13 3 19 6 8 1 4 15 15 6 12 6 12 10 2 10 5 2 5 13 1 5 10 9 11 9 12 3 3 8 8 7 14 10 1 10 11 3 1 5 2 7 17 8 10 10 10 12 16 6 11 3 7 9 19 13 6 13 10 2 17 12 14 10 13 15 20 5 9 10 3 8 10 12 6 14 17 13 13 8 3 2 3 6 8...
output:
1 2 2 2 2 -1 -1 -1 -1 1 2 -1 -1 2 2 2 2 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1
result:
ok 30 numbers
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 73736kb
input:
20 15 30 14 1 14 18 9 18 6 9 2 6 2 10 10 17 11 9 2 16 5 14 10 8 11 20 20 19 3 14 18 7 13 7 15 2 15 12 4 6 13 11 9 13 8 9 15 8 15 7 7 14 14 3 3 10 6 14 9 12 12 1 6 4 2 9 5 14 17 8 14 6 15 10 9 1 4 11 4 1 6 15 18 1 3 1 5 1 9 1 14 4 16 3 12 7 14 2 13 11 7 14 4 4 3 12 1 15 20 15 4 3 14 9 1 13 14 13 4 11...
output:
2 -1 2 2 2 3 -1 1 2 -1 -1 1 -1 2 -1 1 1 -1 2 2 -1 2 2 2 2 -1 -1 2 2 2
result:
wrong answer 6th numbers differ - expected: '2', found: '3'