제출 #748227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748227		amirhoseinfar1385	Inside information (BOI21_servers)	C++17	53 / 100	189 ms	36452 KiB

servers

#include<bits/stdc++.h>
using namespace std;
const int maxn=120000+10;
struct yal{
    int u,v,w;
    int getad(int fu){
        int ret=(fu^u^v);
        return ret;
    }
};

struct quer{
    char c;
    int u,v,w,res;
    quer(){
        res=0;
    }
};
quer allq[maxn];
yal alled[maxn];
vector<int>adj[maxn];
int high[maxn],lca[20][maxn],n,k,now=0,nowq=0,timea=0,par[maxn],dpinc[maxn],dpdec[maxn],val[maxn];
pair<int,int>stf[maxn];

int root(int chi){
    if(chi==par[chi])
    {
        return chi;
    }
    return par[chi]=root(par[chi]);
}

void con(int u,int v){
    int rootu=root(u),rootv=root(v);
    if(rootu!=rootv){
        par[rootu]=rootv;
    }
}

int isc(int u,int v){
    int rootu=root(u),rootv=root(v);
    //cout<<u<<" "<<v<<" "<<rootu<<" "<<rootv<<"\n";
    if(rootu!=rootv){
        return 0;
    }
    return 1;
}

void dfs(int u,int para=0){
    if(u!=1){
        if(val[u]<val[para]){
            dpinc[u]=dpinc[para]+1;
            dpdec[u]=1;
        }
        else{
            dpinc[u]=1;
            dpdec[u]=dpdec[para]+1;
        }
    }
    timea++;
    stf[u].first=timea;
    lca[0][u]=para;
    for(auto x:adj[u]){
        int v=alled[x].getad(u);
        if(v!=para){
            val[v]=alled[x].w;
            high[v]=high[u]+1;
            dfs(v,u);
        }
    }
    stf[u].second=timea;
}

void callca(){
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            lca[i][j]=lca[i-1][lca[i-1][j]];
        }
    }
}

bool zird(int u,int v){
    if(stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second){
        return 1;
    }
    return 0;
}

void solve(int ind){
    int u=allq[ind].u,v=allq[ind].v;
    if(zird(u,v)){
        int di=high[u]-high[v];
        if(dpdec[u]>=di){
            return ;
        }
        else{
            allq[ind].res=0;
            return ;
        }
    }
    if(zird(v,u)){
        int di=high[v]-high[u];
        if(dpinc[v]>=di){
            return ;
        }
        else{
            allq[ind].res=0;
            return ;
        }
    }
    int fu=u,fv=v;
    for(int i=19;i>=0;i--){
        if(lca[i][u]!=0&&!zird(v,lca[i][u])){
            u=lca[i][u];
        }   
    }
    u=lca[0][u];
    int di=high[fv]-high[u];
    if(dpinc[fv]<di){
        allq[ind].res=0;
        return ;
    }
    di=high[fu]-high[u];
    if(dpdec[fu]<di){
        allq[ind].res=0;
        return ;
    }
    if(stf[fv].first>stf[fu].first){
        allq[ind].res=0;
    }
};


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<maxn;i++){
        par[i]=i;
    }
    cin>>n>>k;
    for(int i=0;i<n+k-1;i++){
        char c;
        cin>>c;
        if(c=='S'){
            now++;
            cin>>alled[now].u>>alled[now].v;
            alled[now].w=now;
            adj[alled[now].u].push_back(now);
            adj[alled[now].v].push_back(now);
            con(alled[now].u,alled[now].v);
            continue;
        }
        if(c=='Q'){
            nowq++;
            allq[nowq].c=c;
            cin>>allq[nowq].u>>allq[nowq].v;
            allq[nowq].w=now;
            allq[nowq].res=isc(allq[nowq].u,allq[nowq].v);
            continue;
        }
        return 0;
        nowq++;
        allq[nowq].c=c;
        cin>>allq[nowq].u;
        allq[nowq].w=now;
    }
    dfs(1);
    callca();
    for(int i=1;i<=nowq;i++){
        if(allq[i].c=='Q'){
            solve(i); 
            if(allq[i].res==1){
                cout<<"yes\n";
            }
            else{
                cout<<"no\n";
            }
        }
    }
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0.5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0.5 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0.5 / 17.5