QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#621478 | #5439. Meet in the Middle | kaiyi | WA | 32ms | 35224kb | C++14 | 4.6kb | 2024-10-08 14:47:27 | 2024-10-08 14:47:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
int n,q;
vector<pair<int,int> >A[N];
vector<pair<int,int> >B[N];
vector<pair<int,int> >b[N];
int ans[N*5];
int A_dfn[N],B_dfn[N];
int dfn;
int e[N<<1],tot;
int ST[N<<1][20];
int p[N];
int rdis[N];//B 树到根的距离
int a[N],to_a[N];
int mn[N],mx[N];//A 树的子树区段
void pdfs(int u,int fa){
B_dfn[u] = ++dfn;
e[++tot] = B_dfn[u];
p[B_dfn[u]] = tot;
for(auto v:B[u]){
if(v.first == fa)continue;
rdis[v.first] = rdis[u] + v.second;
pdfs(v.first,u);
e[++tot] = B_dfn[u];
}
}
void init(){
for(int i=1;i<=tot;i++)ST[i][0] = e[i];
for(int i=1;i<20;i++){
for(int j=1;j<=tot;j++){
ST[j][i] = ST[j][i-1];
if(j+(1<<(i-1)) <= tot)ST[j][i] = min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
}
}
}
int log(int len){return 63 - __builtin_clzll(len*1ull);}
int get_dis(int u,int v){
if(u==v)return 0;
//get lca
int ret = 0;
if(p[B_dfn[u]] > p[B_dfn[v]])swap(u,v);
int k = log(p[B_dfn[v]] - p[B_dfn[u]] + 1);
assert(k<20);
int lca = min(ST[p[B_dfn[u]]][k],ST[p[B_dfn[v]] - (1<<k) + 1][k]);
//get dis
ret = rdis[u] + rdis[v] - 2*rdis[lca];
return ret;
}
void dfs(int u,int fa){
A_dfn[u] = ++dfn;
to_a[dfn] = u;
mn[u] = mx[u] = dfn;
for(auto v:A[u]){
if(v.first == fa)continue;
a[v.first] = a[u] + v.second;
dfs(v.first,u);
mx[u] = max(mx[u],mx[v.first]);
}
}
int p1[N<<2],p2[N<<2],w1[N<<2],w2[N<<2],lz[N<<2];
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
void pushup(int x){
int _p[4] = {p1[ls],p2[ls],p1[rs],p2[rs]};
int _w[4] = {w1[ls],w2[ls],w1[rs],w2[rs]};
int dis = 0,rp1 = 0,rp2 = 0,rw1 = 0,rw2 = 0;
for(int i=0;i<3;i++){
for(int j=i+1;j<4;j++){
if(_p[i] == _p[j]){
if(dis < _w[i]){
dis = _w[i];
rp1 = _p[i];rp2 = _p[j];
rw1 = _w[i];rw2 = _w[j];
}
}else{
int d = get_dis(_p[i],_p[j]);
if(dis < d + _w[i] + _w[j]){
dis = d + _w[i] + _w[j];
rp1 = _p[i];rp2 = _p[j];
rw1 = _w[i];rw2 = _w[j];
}
}
}
}
p1[x] = rp1;p2[x] = rp2;
w1[x] = rw1;w2[x] = rw2;
}
void pushdown(int x){
int lazy = lz[x];
lz[x] = 0;
w1[ls] += lazy;w2[ls] += lazy;lz[ls] += lazy;
w1[rs] += lazy;w2[rs] += lazy;lz[rs] += lazy;
}
void build(int x,int l,int r){
if(l==r){
p1[x] = p2[x] = to_a[l];
w1[x] = w2[x] = a[to_a[l]];
return ;
}
build(ls,l,mid);build(rs,mid+1,r);
pushup(x);
// cout<<x<<' '<<l<<' '<<r<<' '<<p1[x]<<' '<<p2[x]<<' '<<w1[x]<<' '<<w2[x]<<'\n';
}
void mdf(int x,int l,int r,int L,int R,int v){
if(L<=l && r<=R){
w1[x] += v;w2[x] += v;
lz[x] += v;
return ;
}
pushdown(x);
if(L<=mid)mdf(ls,l,mid,L,R,v);
if(R>mid)mdf(rs,mid+1,r,L,R,v);
pushup(x);
}
void hg(int u,int fa){
//statistics
// cout<<u<<':'<<p1[1]<<' '<<p2[1]<<' '<<w1[1]<<' '<<w2[1]<<'\n';
for(auto i:b[u]){
ans[i.second] = max(get_dis(i.first,p1[1])+w1[1],get_dis(i.first,p2[1])+w2[1]);
}
for(auto v:A[u]){
if(v.first==fa)continue;
//in
mdf(1,1,n,1,n,v.second);
mdf(1,1,n,mn[v.first],mx[v.first],-2*v.second);
hg(v.first,u);
//out
mdf(1,1,n,mn[v.first],mx[v.first],2*v.second);
mdf(1,1,n,1,n,-v.second);
}
}
void solve(){
cin>>n>>q;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
A[u].push_back({v,w});
A[v].push_back({u,w});
}
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
B[u].push_back({v,w});
B[v].push_back({u,w});
}
for(int i=1,ta,tb;i<=q;i++){
cin>>ta>>tb;
b[ta].push_back({tb,i});
}
//预处理B树的树上距离
pdfs(1,0);dfn=0;
init();
//线段树
//求出根节点答案 build
dfs(1,0);
build(1,1,n);
//换根
hg(1,0);
// cout<<p1[1]<<' '<<p2[1]<<' '<<w1[1]<<' '<<w2[1]<<endl;
// cout<<get_dis(p1[1],p2[1]) + w1[1] + w2[1]<<endl;
//输出
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int aqx = 1;
//cin>>aqx;
while(aqx--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28552kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
6 4 5 3
result:
ok 4 number(s): "6 4 5 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 25780kb
input:
2 1 1 2 1 1 2 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 28720kb
input:
2 1 1 2 1 1 2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 32ms
memory: 35224kb
input:
10000 50000 8101 5996 108427744 5996 7605 870838849 5996 5599 603303696 8101 3006 339377417 8101 6463 442516687 6463 5560 109174079 5560 4063 127596224 3006 1682 947915262 5996 1986 130416311 6463 5455 279771516 6463 2634 516688796 4063 3034 217886863 7605 5092 742375061 5599 2266 193804402 5092 140...
output:
605428585885 515786999416 341010677550 594656594179 364851767304 603433117001 601464348532 535915664344 578179670938 516161934444 634297039260 601246048146 712111878009 539592707192 513426374434 486670314033 504433652298 649476736316 509087792096 495771618350 582467592188 607963406540 529335429169 6...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '605428585885'