Submission #1126984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126984		imarn	Inside information (BOI21_servers)	C++20	0 / 96	31 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};
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);
    }
}
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);
    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(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