QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87608 | #5439. Meet in the Middle | CharlieVinnie | WA | 112ms | 17624kb | C++14 | 3.1kb | 2023-03-13 21:13:22 | 2023-03-13 21:13:24 |
Judging History
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'