QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696333 | #5439. Meet in the Middle | TianShuiXingHe | WA | 0ms | 33424kb | C++17 | 5.6kb | 2024-10-31 22:08:29 | 2024-10-31 22:08:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace basic{
// #define int long long
#define ll long long
#define uint unsigned int
#define per(i,a,b) for(int i=(a);i<=(b);i++)
#define perr(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define rep(i,b,a) for(int i=(b);i>=(a);i--)
#define epb emplace_back
#define bit(x) (1ll<<(x))
#define all(x,l,r) &(x)[l],&(x)[r]+1
#define vall(x) (x).begin(),(x).end()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define pc(x) putchar(x)
#define turn(x) (x-'a'+1)
#define cto const auto
template <class T> bool chkmn(T &x,T y){return x>y?(x=y,1):0;}
template <class T> bool chkmn(T &x,T y,T z){return y<z?(x=y,1):(x=z,0);}
template <class T> bool chkmx(T &x,T y){return x<y?(x=y,1):0;}
template <class T> bool chkmx(T &x,T y,T z){return y>z?(x=y,1):(x=z,0);}
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){
int x=0,f=1;char ch=nc();
while(ch<48||ch>57){if(ch=='-') f=-1;ch=nc();}
while(ch>=48&&ch<=57) x=x*10+ch-48,ch=nc();
return x*f;
}
char cread(){
char ch=nc();
while(ch<'A'||ch>'z') ch=nc();
return ch;
}
void write(int x){
if(x<0) pc('-'),x=-x;
if(x>9) write(x/10);
pc(x%10+'0');
}
void print(string s,char op=0){for(auto x:s) pc(x);op&&pc(op);}
void print(int x,char op=0){write(x);op&&pc(op);}
}
using namespace basic;
namespace fisher{
bool mbe;void cntime();
const int N=1e5+5,M=5e5+5;
struct edge{
int v;ll w;
edge(int _v,ll _w){
v=_v;w=_w;
}
};
struct tree{
int tot,dfn[N];
int add(int u){
return dfn[u]=++tot;
}
void init(int n){
tot=0;
}
}g[3];
int n;
vector <edge> e[3][N];
struct st_lca{
#define get(x,y) (dep[x]<dep[y]?(x):(y))
int lg[N],st[30][N],dep[N];
ll dis[N];
void dfs(int u,int fa){
st[0][g[2].add(u)]=fa;
dep[u]=dep[fa]+1;
for(auto [v,w]:e[2][u]) if(v!=fa){
dis[v]=dis[u]+w;
dfs(v,u);
}
}
void build(int n){
dfs(1,0);
per(i,2,n) lg[i]=lg[i>>1]+1;
per(i,1,lg[n]) per(j,1,n-bit(i)+1)
st[i][j]=get(st[i-1][j],st[i-1][j+bit(i-1)]);
}
int query(int l,int r){
int k=lg[r-l+1];
return get(st[k][l],st[k][r-bit(k)+1]);
}
int lca(int u,int v){
if(u==v) return u;
u=g[2].dfn[u];v=g[2].dfn[v];
if(u>v) swap(u,v);
return query(u+1,v);
}
ll dist(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
#undef get
}st;
struct info{
int x,y;ll dx,dy,dis;
info(){x=y=dx=dy=dis=0;}
info(int _p,ll _d){x=y=_p;dx=dy=dis=_d;}
info(int _x,int _y,ll _dx,ll _dy){
x=_x;y=_y;dx=_dx;dy=_dy;
dis=st.dist(x,y)+dx+dy;
}
friend bool operator <(const info &x,const info &y){
return x.dis<y.dis;
}
friend info operator +(info x,info y){
if(x.x==y.x&&y.x==y.y) return info(x.x,y.x,x.dx,y.dy);
info z=max(x,y);
chkmx(z,info(x.x,y.x,x.dx,y.dx));
chkmx(z,info(x.x,y.y,x.dx,y.dy));
chkmx(z,info(x.y,y.x,x.dy,y.dx));
chkmx(z,info(x.y,y.y,x.dy,y.dy));
return z;
}
};
int T,m;
ll dis[N],ans[M];
int rev[N],siz[N];
vector <edge> q[N];
struct seg{
#define mid (((l)+(r))>>1)
info t[N<<2];ll tag[N<<2];
void push_up(int i){
t[i]=t[ls(i)]+t[rs(i)];
}
void modify(int i,ll k){
t[i].dx+=k;t[i].dy+=k;
t[i].dis+=k*(1+(t[i].x!=t[i].y));
tag[i]+=k;
}
void push_down(int i){
if(!tag[i]) return;
modify(ls(i),tag[i]);
modify(rs(i),tag[i]);
tag[i]=0;
}
void update(int nl,int nr,int l,int r,int i,ll k){
if(nl<=l&&r<=nr) return modify(i,k);
push_down(i);
if(nl<=mid) update(nl,nr,l,mid,ls(i),k);
if(mid<nr) update(nl,nr,mid+1,r,rs(i),k);
push_up(i);
}
info query(){return t[1];}
void build(int i,int l,int r){
t[i]=info();tag[i]=0;
if(l==r){
int id=rev[l];
t[i]=info(id,dis[id]);
return;
}
build(ls(i),l,mid);
build(rs(i),mid+1,r);
push_up(i);
}
#undef mid
}t;
void dfs(int u,int fa){
rev[g[1].add(u)]=u;siz[u]=1;
for(auto [v,w]:e[1][u]) if(v!=fa){
dis[v]=dis[u]+w;
dfs(v,u);
siz[u]+=siz[v];
}
}
void add(int op,int u,int v,ll w){
e[op][u].epb(v,w);
e[op][v].epb(u,w);
}
void init(){
per(i,1,n) q[i].clear();
per(i,1,2) g[i].init(n);
per(op,1,2) per(i,1,n) e[op][i].clear();
per(op,1,2) per(i,2,n){
int u,v;ll w;
cin>>u>>v>>w;
add(op,u,v,w);
}
dfs(1,0);
st.build(n);
}
void solve(int u,int fa){
for(auto [v,id]:q[u]){
info p=t.query();
chkmx(ans[id],st.dist(v,p.x)+p.dx,st.dist(v,p.y)+p.dy);
}
for(auto [v,w]:e[1][u]) if(v!=fa){
int l=g[1].dfn[v],r=l+siz[v]-1;
t.modify(1,w);
t.update(l,r,1,n,1,-2*w);
solve(v,u);
t.modify(1,-w);
t.update(l,r,1,n,1,2*w);
}
}
void main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// for(cin>>T;T--;){
cin>>n;init();
cin>>m;
per(i,1,m){
int u,v;
cin>>u>>v;
q[u].epb(v,i);
}
t.build(1,1,n);
solve(1,0);
per(i,1,m) cout<<ans[i]<<'\n';
// }
return cntime();
}
bool mbd;void cntime(){
cerr<<"Memory: "<<abs(&mbd-&mbe)/1048476.0<<" MB\n";
cerr<<"Time: "<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
}}
signed main(){
// freopen("move1.in","r",stdin);
// freopen("move.out","w",stdout);
fisher::main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 33424kb
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'