QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696333#5439. Meet in the MiddleTianShuiXingHeWA 0ms33424kbC++175.6kb2024-10-31 22:08:292024-10-31 22:08:31

Judging History

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

  • [2024-10-31 22:08:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:33424kb
  • [2024-10-31 22:08:29]
  • 提交

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'