QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100053 | #5439. Meet in the Middle | 1kri | WA | 142ms | 60648kb | C++14 | 5.2kb | 2023-04-24 15:51:13 | 2023-04-24 15:51:17 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
const ll inf=1000000000000000ll;
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int n,q,a[500005],b[500005];
vector<int> qid[500005];
ll ans[500005];
ll val[100005];
struct qwq{
int u[200005],v[200005],w[200005],first[100005],nxt[200005];
int idx,dfn[200005];
void dfs(int now,int fa){
dfn[now]=++idx;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)dfs(v[i],now);
return;
}
void init(){
for (int i=1;i<n;i++){
u[i]=read(),v[i]=read(),w[i]=read();
nxt[i]=first[u[i]],first[u[i]]=i;
u[i+n]=v[i],v[i+n]=u[i],w[i+n]=w[i];
nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
}
dfs(1,0);
return;
}
}qwq1,qwq2;
namespace T2{
int u[200005],v[200005],w[200005],first[100005],nxt[200005];
int idx,ord[200005];
int log_2[200005];
ll sum[200005];
ll st[20][200005];
void dfs(int now,int f,ll s){
sum[now]=s;
++idx;
ord[now]=idx;
st[0][idx]=s;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=f){
dfs(v[i],now,s+w[i]);
++idx;
st[0][idx]=s;
}
return;
}
ll dis(int a,int b){
int l=min(ord[a],ord[b]),r=max(ord[a],ord[b]);
int w=log_2[r-l+1];
return val[a]+val[b]+sum[a]+sum[b]-2*min(st[w][l],st[w][r-(1<<w)+1]);
}
struct node{
int a,b;
ll c;
node(){
a=b=-1;
c=0;
return;
}
node operator +(const node &y)const{
node ans;
if (c>=y.c)ans.a=a,ans.b=b,ans.c=c;
else ans.a=y.a,ans.b=y.b,ans.c=y.c;
ll d=0;
d=dis(a,y.a);
if (d>ans.c)ans.a=a,ans.b=y.a,ans.c=d;
d=dis(a,y.b);
if (d>ans.c)ans.a=a,ans.b=y.b,ans.c=d;
d=dis(b,y.a);
if (d>ans.c)ans.a=b,ans.b=y.a,ans.c=d;
d=dis(b,y.b);
if (d>ans.c)ans.a=b,ans.b=y.b,ans.c=d;
return ans;
}
};
node tree[262144];
void pushup(int now){
tree[now]=tree[now*2]+tree[now*2+1];
return;
}
void build(int now,int nowl,int nowr){
if (nowl==nowr){
tree[now].a=tree[now].b=nowl,tree[now].c=0;
return;
}
int mid=(nowl+nowr)/2;
build(now*2,nowl,mid);
build(now*2+1,mid+1,nowr);
pushup(now);
return;
}
int upd_fg;
void upd(int now,int nowl,int nowr,int pos){
if (nowl==nowr){
tree[now].a=tree[now].b=nowl,tree[now].c=0;
upd_fg=1;
return;
}
int mid=(nowl+nowr)/2;
if (pos<=mid)upd(now*2,nowl,mid,pos);
else upd(now*2+1,mid+1,nowr,pos);
if (upd_fg==1){
node qwq=tree[now];
pushup(now);
if (tree[now].a==qwq.a&&tree[now].b==qwq.b&&tree[now].c==qwq.c)upd_fg=0;
}
return;
}
void init(){
qwq2.init();
for (int i=1;i<n;i++){
u[i]=qwq2.dfn[qwq2.u[i]],v[i]=qwq2.dfn[qwq2.v[i]],w[i]=qwq2.w[i];
nxt[i]=first[u[i]],first[u[i]]=i;
u[i+n]=v[i],v[i+n]=u[i],w[i+n]=w[i];
nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
}
dfs(1,0,0);
for (int i=2;i<=idx;i++)log_2[i]=log_2[i/2]+1;
for (int w=1;w<20;w++)
for (int i=1;i+(1<<w)-1<=idx;i++)
st[w][i]=min(st[w-1][i],st[w-1][i+(1<<(w-1))]);
build(1,1,n);
return;
}
}
namespace T1{
int u[200005],v[200005],w[200005],first[100005],nxt[200005];
void init(){
qwq1.init();
for (int i=1;i<n;i++){
u[i]=qwq1.dfn[qwq1.u[i]],v[i]=qwq1.dfn[qwq1.v[i]],w[i]=qwq1.w[i];
nxt[i]=first[u[i]],first[u[i]]=i;
u[i+n]=v[i],v[i+n]=u[i],w[i+n]=w[i];
nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
}
return;
}
int book[100005];
int sz[100005],qwqn,rt;
void getrt(int now,int fa){
sz[now]=1;
int mx=0;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa&&book[v[i]]==0){
getrt(v[i],now);
sz[now]+=sz[v[i]];
mx=max(mx,sz[v[i]]);
}
mx=max(mx,qwqn-sz[now]);
if (2*mx<=qwqn)rt=now;
return;
}
int tot,id[100005];
ll sum[100005];
void dfs(int now,int f,ll s){
id[++tot]=now;
sum[now]=s;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=f&&book[v[i]]==0)dfs(v[i],now,s+w[i]);
return;
}
ll ask(int x){
int a=T2::tree[1].a,b=T2::tree[1].b;
return max(T2::dis(x,a),T2::dis(x,b))-val[x];
}
void get_ans(int now){
for (int i=0;i<(int)qid[now].size();i++){
int id=qid[now][i];
ans[id]=max(ans[id],sum[now]+ask(b[id])-inf);
}
return;
}
void work(int now){
book[now]=1;
getrt(now,0);
tot=0;
dfs(now,0,0);
for (int i=1;i<=tot;i++){
val[id[i]]=sum[id[i]]+inf;
T2::upd(1,1,n,id[i]);
}
get_ans(now);
for (int i=first[now];i;i=nxt[i]){
if (book[v[i]]==1)continue;
tot=0;
dfs(v[i],now,w[i]);
for (int j=1;j<=tot;j++){
val[id[j]]=0;
T2::upd(1,1,n,id[j]);
}
for (int j=1;j<=tot;j++)get_ans(id[j]);
for (int j=1;j<=tot;j++){
val[id[j]]=sum[id[j]]+inf;
T2::upd(1,1,n,id[j]);
}
}
tot=0;
dfs(now,0,0);
for (int i=1;i<=tot;i++){
val[id[i]]=0;
T2::upd(1,1,n,id[i]);
}
for (int i=first[now];i;i=nxt[i])
if (book[v[i]]==0){
qwqn=sz[v[i]];
getrt(v[i],now);
work(rt);
}
return;
}
}
int main(){
n=read(),q=read();
T1::init();
T2::init();
for (int i=1;i<=q;i++){
a[i]=qwq1.dfn[read()],b[i]=qwq2.dfn[read()];
qid[a[i]].push_back(i);
}
T1::work(1);
for (int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 42760kb
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: 3ms
memory: 40504kb
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: 40496kb
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: 142ms
memory: 60648kb
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:
577513104133 589399566619 492600773305 566741112427 444402850517 575517635249 414355112603 470578184035 441869104571 579294141722 486465057285 510182737172 732135578491 751051156566 458998849513 450769875575 597646482564 436174420431 432118630526 502230128416 640407007170 480308091159 631250113261 5...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '577513104133'