제출 #1126163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126163		imarn	Inside information (BOI21_servers)	C++20	0 / 96	34 ms	5048 KiB

servers

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define t3 tuple<int,int,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=120050;
vector<pii>g[mxn];
int d[mxn]{0},a[mxn]{0},up[mxn][20]{0},mx[mxn][20]{0},mn[mxn][20]{0},pr[mxn]{0};
int sz[mxn]{0},head[mxn]{0},id[mxn]{0},cur=0;
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
void uni(int u,int v){
    if(get(u)==get(v))return;
    u=get(u),v=get(v);
    if(d[u]>d[v])swap(u,v);
    pr[v]=u;
}
void dfs(int u,int p,int x){
    up[u][0]=p;a[u]=x;sz[u]=1;
    mx[u][0]=mn[u][0]=a[u]-a[p];
    for(int i=1;i<20;i++)up[u][i]=up[up[u][i-1]][i-1];
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        d[v]=d[u]+1;
        dfs(v,u,w);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cur;
    int hv=-1;
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        if(hv==-1||sz[hv]<sz[v])hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto [v,w]:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}
struct lazy{
    ll t[4*mxn]{0},lz[4*mxn]{0};
    void push(int i,int l,int r){
        t[i]+=lz[i]*(r-l+1);
        if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]+=v;push(i,l,r);return;
        }int m=(l+r)>>1;
        update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
        t[i]=t[2*i]+t[2*i+1];
    }
    int qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return 0;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
    }
}sg[2];
int getlca(int a,int b){
    if(d[a]>d[b])swap(a,b);
    for(int i=19;i>=0;i--)if(d[b]-(1<<i)>=d[a])b=up[b][i];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
    return up[a][0];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    vector<t3>qr;iota(pr,pr+n+1,0);
    for(int i=0;i<n+k-1;i++){
        char s;cin>>s;
        if(s=='S'){int a,b;cin>>a>>b;qr.pb({0,a,b});}
        if(s=='Q'){int a,b;cin>>a>>b;qr.pb({1,a,b});}
        if(s=='C'){int a;cin>>a;qr.pb({2,a,0});}
    }int cu=0;
    for(auto [o,u,v]:qr){
        if(o)continue;
        g[u].pb({v,++cu});
        g[v].pb({u,cu});
    }dfs(1,1,0);hld(1,1,1);
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            mx[i][j]=max(mx[i][j-1],mx[up[i][j-1]][j-1]);
            mn[i][j]=min(mn[i][j-1],mn[up[i][j-1]][j-1]);
        }
    }
    for(int i=1;i<=n;i++)cout<<mx[i][0]<<' ';cout<<'\n';
    for(auto [o,u,v]:qr){
        if(!o)uni(u,v);
        else if(o==1){
            bool ok=1;
            if(get(u)!=get(v))ok=0;
            int lca=getlca(u,v);
            int mxd=-1e9,mnd=1e9;
            for(int i=19;i>=0;i--){
                if(d[up[u][i]]>=d[lca]+1)mnd=min(mnd,mn[u][i]),u=up[u][i];
                if(d[up[v][i]]>=d[lca]+1)mxd=max(mxd,mx[v][i]),v=up[v][i];
            }if(mnd<0||mxd>0)ok=0;
            if(a[u]<a[v])ok=0;
            cout<<(ok?"yes\n":"no\n");
        }
    }
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 2
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12
• Subtask 11: 0 / 17
• Subtask 12: 0 / 17