QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100053#5439. Meet in the Middle1kriWA 142ms60648kbC++145.2kb2023-04-24 15:51:132023-04-24 15:51:17

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-24 15:51:17]
  • 评测
  • 测评结果:WA
  • 用时:142ms
  • 内存:60648kb
  • [2023-04-24 15:51:13]
  • 提交

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'