QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692564 | #5439. Meet in the Middle | wdnmdwrnmmp | WA | 0ms | 17488kb | C++14 | 4.3kb | 2024-10-31 14:42:53 | 2024-10-31 14:42:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
using i64=unsigned long long;
void chmax(i64 &x,i64 y){
if(y>x){
x=y;
}
}
const int N=1e5+5;
int n;
namespace tree0{
vector<pi> G[N];
int dfn[N], dfc;
i64 dep[N];
int mn[17][N];
void link(int u,int v,int w){
G[u].pb(v, w);
G[v].pb(u, w);
}
void dfs(int u,int p){
dfn[u]=++dfc;
mn[0][dfc]=p;
for(auto [v,w]:G[u]){
if(v!=p){
dep[v]=dep[u]+w;
dfs(v, u);
}
}
}
int get(int u,int v){
return dfn[u]<dfn[v]? u: v;
};
void init(){
dfs(1, 0);
rep(i,1,16){
rep(j,1,n-(1<<i)+1){
mn[i][j]=get(mn[i-1][j], mn[i-1][j+(1<<(i-1))]);
}
}
}
int LCA(int u,int v){
if(u==v){
return u;
}
if((u=dfn[u])>(v=dfn[v])){
swap(u, v);
}
int lg=__lg(v-(u++));
return get(mn[lg][u], mn[lg][v-(1<<lg)+1]);
}
i64 dis(int u,int v){
return dep[u]+dep[v]-dep[LCA(u,v)]*2;
}
void clear(int n){
rep(i,1,n){
G[i].clear();
}
dfc=0;
}
}
namespace tree1{
vector<pi> G[N], Q[N];
i64 ans[500005];
bool vis[N];
void link(int u,int v,int w){
G[u].pb(v,w);
G[v].pb(u,w);
}
int sz[N], totsz, hv;
i64 dep[N];
vi tmp;
void dfs0(int u,int p){
sz[u]=1;
int mxsz=0;
for(const auto &[v,w]:G[u]){
if(v!=p && !vis[v]){
dfs0(v, u);
sz[u]+= sz[v];
mxsz=max(mxsz, sz[v]);
}
}
mxsz=max(mxsz, totsz-sz[u]);
if(mxsz*2<=totsz){
hv=u;
}
}
void dfs1(int u,int p){
tmp.pb(u);
for(const auto &[v,w]:G[u]){
if(v!=p && !vis[v]){
dep[v]=dep[u]+w;
dfs1(v, u);
}
}
}
i64 dis(int u,int v){
return tree0::dis(u, v)+dep[u]+dep[v];
}
vector< tuple<int,int,i64> > prt, srt;
vector<vi> S;
void slv(int u){
dfs0(u, 0);
u=hv;
vis[u]=1;
prt.clear();
srt.clear();
S.clear();
S.pb((vi){u});
dep[u]=0;
for(auto [v,w]:G[u]){
if(!vis[v]){
dep[v]=w;
dfs1(v, u);
S.resize(S.size()+1);
swap(S.back(), tmp);
}
}
prt.resize(S.size());
rep(i,0,(int)S.size()-1){
int du=S[i][0], dv=S[i][0];
i64 ddis=0;
for(int x:S[i]){
i64 d0=dis(du, x), d1=dis(dv, x);
if(d0<d1){
swap(d0, d1);
swap(du, dv);
}
if(d0>ddis){
ddis=d0;
dv=x;
}
}
prt[i]={du, dv, ddis};
}
srt=prt;
rep(i,1,(int)S.size()-1){
auto &[du,dv,ddis]=prt[i];
for(int x:{get<0>(prt[i-1]), get<1>(prt[i-1])}){
i64 d0=dis(du, x), d1=dis(dv, x);
if(d0<d1){
swap(d0, d1);
swap(du, dv);
}
if(d0>ddis){
ddis=d0;
dv=x;
}
}
}
per(i,(int)S.size()-2,0){
auto &[du,dv,ddis]=srt[i];
for(int x:{get<0>(srt[i+1]), get<1>(srt[i+1])}){
i64 d0=dis(du, x), d1=dis(dv, x);
if(d0<d1){
swap(d0, d1);
swap(du, dv);
}
if(d0>ddis){
ddis=d0;
dv=x;
}
}
}
vi V;
rep(i,0,(int)S.size()-1){
V.clear();
if(i!=0){
V.pb(get<0>(prt[i-1]));
V.pb(get<1>(prt[i-1]));
}
if(i!=(int)S.size()-1){
V.pb(get<0>(srt[i+1]));
V.pb(get<1>(srt[i+1]));
}
for(int x:S[i]){
if(Q[x].empty()){
continue;
}
for(const auto &[y,id]:Q[x]){
for(int z:V){
chmax(ans[id], tree0::dis(y, z)+dep[x]+dep[z]);
}
}
}
}
int psz=totsz;
for(const auto &[v,w]:G[u]){
if(!vis[v]){
totsz=(sz[v]<sz[u]? sz[v]: psz-sz[u]);
slv(v);
}
}
}
void clear(int n,int q){
rep(i,1,n){
G[i].clear(), Q[i].clear();
vis[i]=0;
}
fill(ans+1, ans+q+1, 0);
}
}
void solve(){
cin>>n;
rep(i,1,n-1){
int u,v,w; cin>>u>>v>>w;
tree0::link(u, v, w);
}
tree0::init();
rep(i,1,n-1){
int u,v,w; cin>>u>>v>>w;
tree1::link(u, v, w);
}
int q; cin>>q;
rep(i,1,q){
int x,y; cin>>x>>y;
tree1::Q[y].pb(x, i);
}
tree1::totsz=n;
tree1::slv(1);
rep(i,1,q){
cout<< tree1::ans[i] <<'\n';
}
tree0::clear(n);
tree1::clear(n, q);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 17488kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
5
result:
wrong answer 1st numbers differ - expected: '6', found: '5'