QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692620 | #5439. Meet in the Middle | zwh2008 | WA | 3ms | 33740kb | C++14 | 4.1kb | 2024-10-31 14:48:02 | 2024-10-31 14:48:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,ll>;
#define fi first
#define se second
bool ST;
const int N=1e5+5;
const ll inf=1e16;
namespace IO {
const int SIZE=(1<<21)+1;
char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f, qr;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
inline void putc(char x){*oS++=x;if(oS==oT)flush();}
template <class I>
inline void read(I &x){
for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
}
template <class I>
inline void print(I x){
if(!x)putc('0');if(x<0)putc('-'),x=-x;
while(x)qu[++qr]=x%10+'0',x/=10;
while(qr)putc(qu[qr --]);
}
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::putc;
using IO::print;
int n,m,Rt,sn,sz[N],Fa[N],dep[N],L[N],R[N],ps[N];
ll D[20][N];
bool del[N];
vector<pi>e[N];
vector<int>E[N];
struct Tree{
int sn,mx[20][N],L[N],fa[N],dep[N];
ll d[N];
vector<pi>e[N];
inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
inline int lca(int x,int y) {
if(x==y)return x;x=L[x],y=L[y];
if(x>y)swap(x,y);int k=__lg(y-x);
return fa[Min(mx[k][x+1],mx[k][y-(1<<k)+1])];
}
inline ll dis(int x,int y){return !x||!y?-inf:d[x]+d[y]-2*d[lca(x,y)];}
void dfs(int x,int p) {
L[x]=++sn,fa[x]=p,dep[x]=dep[p]+1,mx[0][sn]=x;int y;
for(pi i:e[x])if((y=i.fi)!=p)d[y]=d[x]+i.se,dfs(y,x);
}
void init() {
for(int i=1;i<=n;i++)e[i].clear();
for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),e[x].push_back({y,z}),e[y].push_back({x,z});
sn=0,d[1]=0,dfs(1,0);
for(int i=1;1<<i<=n;i++)for(int j=1;j<=n-(1<<i)+1;j++)mx[i][j]=Min(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
}
}T;
struct info{
pi x,y;ll d;
info(){x=y={0,0},d=-inf;}
info(pi a,pi b){x=a,y=b,d=T.dis(a.fi,b.fi)+a.se+b.se;}
bool operator<(const info t)const{return d<t.d;}
ll calc(int t){return max(T.dis(x.fi,t)+x.se,T.dis(y.fi,t)+y.se);}
void upd(pi t) {
if(!t.fi)return;
info d1=info(t,x),d2=info(t,y);
if((d1.d>d&&d1.d>d2.d)||y.fi==0)y=t,d=d1.d;
else if(d2.d>d||x.fi==0)x=t,d=d2.d;
}
friend info operator+(const info a,const info b) {
info d1=info(a.x,b.x),d2=info(a.x,b.y),d3=info(a.y,b.x),d4=info(a.y,b.y);
return max(max(a,b),max(max(d1,d2),max(d3,d4)));
}
}f[N],g[N],h[N];
void gsz(int x,int p){sz[x]=1;for(pi i:e[x])if(i.fi!=p&&!del[i.fi])gsz(i.fi,x),sz[x]+=sz[i.fi];}
void grt(int tot,int&rt,int x,int p) {
int mx=0,y;for(pi i:e[x])if(!del[y=i.fi]&&y!=p)grt(tot,rt,y,x),mx=max(mx,sz[y]);
if(max(mx,tot-sz[x])*2<=tot)rt=x;
}
void getd(int x,int p,int nd){for(pi i:e[x])if(i.fi!=p&&dep[i.fi]>nd)D[nd][i.fi]=D[nd][x]+i.se,getd(i.fi,x,nd);}
void upd(int x,info&t,int nd){for(int i=L[x];i<=R[x];i++)t.upd({ps[i],D[nd][ps[i]]});}
void slv(int x,int p,int nd) {
int rt=0;gsz(x,0),grt(sz[x],rt,x,0),del[rt]=1,dep[rt]=nd;
if(!p)Rt=rt;else E[p].push_back(rt);
L[rt]=++sn,ps[sn]=rt,Fa[rt]=p;
for(pi i:e[rt])if(!del[i.fi])slv(i.fi,rt,nd+1);
R[rt]=sn;
}
void solve() {
read(n);
for(int i=1;i<=n;i++)e[i].clear(),E[i].clear(),del[i]=0;
for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),e[x].push_back({y,z}),e[y].push_back({x,z});
T.init(),Rt=sn=0,slv(1,0,0);
for(int i=1;i<=n;i++) {
D[dep[i]][i]=0,getd(i,0,dep[i]);
g[i]=info(),upd(i,g[i],dep[i]);
info now({i,0},{i,0});
for(int y:E[i])f[y]=now,h[y]=info(),upd(y,h[y],dep[i]),now=now+h[y];
now=info();for(int j=E[i].size()-1;~j;j--)f[E[i][j]]=f[E[i][j]]+now,now=now+h[E[i][j]];
}
read(m);
while(m--) {
int x,y;read(x),read(y);ll ans=g[x].calc(y);
for(int i=x;i!=Rt;i=Fa[i])ans=max(ans,D[dep[i]-1][x]+f[i].calc(y));
print(ans),putc('\n');
}
}
bool ED;
int main() {
cerr<<"Memory: "<<(&ST-&ED)/1024.0/1024.0<<" MB\n";
int tt=1;//read(tt);
while(tt--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 33740kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
12
result:
wrong answer 1st numbers differ - expected: '6', found: '12'