QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87608#5439. Meet in the MiddleCharlieVinnieWA 112ms17624kbC++143.1kb2023-03-13 21:13:222023-03-13 21:13:24

Judging History

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

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

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; using ll = long long;
const int N=1e5+5,M=5e5+5; using pii = pair<ll,int>;
int n,Q,head[N],nxt[N*2],to[N*2],edge[N*2],tot,eucnt,lg2[N*2],st[N],ed[N],dfn[N],dfed[N],lis[N],lcnt; vector<pii> cp[N],qry[N]; pii eu[N*2][20]; ll dep[N],ddep[N],ans[M];
inline void add(int x,int y,int z) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; edge[tot]=z; }
void dfs2(int u,int pa){
	eu[st[u]=++eucnt][0]=pii(dep[u],u); lis[dfn[u]=++lcnt]=u;
	for(int e=head[u];e;e=nxt[e]){
		int v=to[e]; if(v==pa) continue;
		dep[v]=dep[u]+edge[e]; dfs2(v,u);
		eu[++eucnt][0]=pii(dep[u],u);
	}
	ed[u]=eucnt; dfed[u]=lcnt;
}
int lca(int x,int y){
	if(st[x]>st[y]) swap(x,y);
	int l=st[x],r=ed[y],k=lg2[r-l+1]; int res=min(eu[l][k],eu[r-(1<<k)+1][k]).second; return res;
}
ll dist(int x,int y) { ll res=dep[x]+dep[y]+ddep[x]+ddep[y]-2*dep[lca(x,y)]; /*printf("dist(%d,%d)=%lld\n",x,y,res);*/ return res; }
class STree{
	class FTree{ int n; ll c[N]; public: void init(int _n) { n=_n; };
		inline void poke(int x,int y) { while(x<=n) c[x]+=y,x+=x&(-x); } inline ll peek(int x) { ll r=0; while(x) r+=c[x],x-=x&(-x);; return r; }
	}T;
	int n,a[N][2];
	#define k1 k<<1
	#define k2 k<<1|1
	ll Dist(int x,int y) { return dist(x,y)+T.peek(x)+T.peek(y); }
	void update(int k){
		ll d=0,td=0; For(i,0,1) For(j,0,1) if((td=Dist(a[k1][i],a[k2][j]))>d) d=td,a[k][0]=a[k1][i],a[k][1]=a[k2][j];
	}
	void build(int k,int l,int r){
		if(l==r) return a[k][0]=a[k][1]=lis[l],void();
		int mid=(l+r)>>1; build(k1,l,mid); build(k2,mid+1,r); update(k);
	}
	void modify(int k,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return;
		int mid=(l+r)>>1; if(ql<=mid) modify(k1,l,mid,ql,qr);; if(mid+1<=qr) modify(k2,mid+1,r,ql,qr);; update(k);
	}
public:
	void build(int _n) { n=_n; T.init(n); build(1,1,n); }
	void modify(int l,int r,int w) { T.poke(1,w); T.poke(l,-2*w); T.poke(r+1,2*w); modify(1,1,n,l,r); }
	ll query(int v) { /*printf("query: %d,%d\n",a[1][0],a[1][1]);*/ return max(Dist(v,a[1][0]),Dist(v,a[1][1]))-(ddep[v]+T.peek(dfn[v])); }
}T;
void dfs1(int u,int pa){
	for(auto qr:qry[u]) ans[qr.second]=T.query(qr.first);
	for(auto pr:cp[u]){
		int v=pr.first, e=pr.second; if(v==pa) continue;
		T.modify(dfn[v],dfed[v],e); dfs1(v,u); T.modify(dfn[v],dfed[v],-e);
	}
}
void dfs0(int u,int pa){
	for(auto pr:cp[u]){
		int v=pr.first; if(v!=pa) ddep[v]=ddep[u]+pr.second,dfs0(v,u);
	}
}
int main(){
	cin>>n>>Q;
	For(i,1,n-1) { int x,y,z; cin>>x>>y>>z; cp[x].emplace_back(y,z); cp[y].emplace_back(x,z); }
	For(i,1,n-1) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); }
	For(i,1,Q) { int x,y; cin>>x>>y; qry[x].emplace_back(y,i); }
	dep[1]=0; dfs2(1,0); lg2[1]=0; For(i,2,eucnt) lg2[i]=lg2[i>>1]+1;
	//~ cout<<dist(1,2)<<'\n';
	For(j,1,lg2[eucnt]) For(i,1,eucnt-(1<<j)+1) eu[i][j]=min(eu[i][j-1],eu[i+(1<<(j-1))][j-1]);
	ddep[1]=0; dfs0(1,0); T.build(n); dfs1(1,0); For(i,1,Q) cout<<ans[i]<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8852kb

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: 4ms
memory: 7956kb

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: 4ms
memory: 8048kb

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: 112ms
memory: 17624kb

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:

645986470153
788732552488
691950458996
634759597877
637504255122
644301011147
845029362985
668525235888
641052211706
789912091450
883672145211
725839822988
925389296928
938364073152
755100587841
722803541582
792516390107
889257882927
745757784935
722583874790
832655304595
681276326798
682629688683
6...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '645986470153'