QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100052 | #5439. Meet in the Middle | 1kri | WA | 145ms | 60408kb | C++14 | 5.2kb | 2023-04-24 15:49:55 | 2023-04-24 15:49:58 |
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];
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];
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: 1ms
memory: 40424kb
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: 40428kb
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: 40436kb
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: 145ms
memory: 60408kb
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:
408383167497 397460134693 188240491388 405059835653 385747049688 405693200992 263431852676 311581799291 332465794816 347951134210 279821524032 382160269275 418246805062 437162383137 259995957842 269266801904 283757709135 262266054133 256111603891 344663581427 326518233741 363025496356 386899037165 4...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '408383167497'