제출 #748552

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

servers

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+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],n,k,now=0,nowq=0,timea=0,dpinc[maxn],dpdec[maxn],val[maxn];
pair<int,int>stf[maxn];
int kaf=(1<<17);

struct segpaeen{
	set<pair<int,int>>seg[(1<<18)];
	void upd(int i,int l,int r,int tl,int tr,pair<int,int> w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			if(w.first>0){
				seg[i].insert(w);
				return ;
			}
			else{
				w.first=-w.first;
				seg[i].erase(w);
				return ;
			}
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
	pair<int,int> pors(int i){
		if(i==0){
			return make_pair(0,0);
		}
		pair<int,int> ret=pors((i>>1));
		if((int)seg[i].size()==0){
			return ret;
		}
		ret=max(ret,(*seg[i].rbegin()));
		return ret;
	}
}seg1;

struct segpo{
	struct node{
		vector<int>v;
		vector<int>fen;
		int sz;
		void create(){
			fen.resize((int)v.size()+3);
			sz=fen.size();
		}
		void upd(int i){
			while(i<sz){
				fen[i]++;
				i+=(-i)&i;
			}
		}
		int pors(int i){
			int ret=0;
			while(i>0){
				ret+=fen[i];
				i-=(-i)&i;
			}
			return ret;
		}
	};
	node seg[(1<<18)];
	void aval(int i,int w){
		if(i==0){
			return ;
		}
		seg[i].v.push_back(w);
		return aval((i>>1),w);
	}
	void pre(){
		for(int i=1;i<(1<<18);i++){
			seg[i].v.push_back(-1);
			sort(seg[i].v.begin(),seg[i].v.end());
			seg[i].v.resize(unique(seg[i].v.begin(),seg[i].v.end())-seg[i].v.begin());
			seg[i].create();
		}
	}
	void upd(int i,int w){
		if(i==0){
			return ;
		}
		int p=lower_bound(seg[i].v.begin(),seg[i].v.end(),w)-seg[i].v.begin();
		seg[i].upd(p);
		upd((i>>1),w);
	}
	int pors(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr)
		{
			return 0;
		}
		if(l>=tl&&r<=tr){
			int p=upper_bound(seg[i].v.begin(),seg[i].v.end(),w)-seg[i].v.begin();
			int ret=seg[i].pors(p-1);
			return ret;
		}
		int m=(l+r)>>1;
		int ret=pors((i<<1),l,m,tl,tr,w)+pors((i<<1)^1,m+1,r,tl,tr,w);
		return ret;
	}
}seg2;










void dfs(int u,int para=0){
    if(u!=1){
        if(val[u]<val[para]){
            dpinc[u]=dpinc[para];
            dpdec[u]=para;
        }
        else{
            dpinc[u]=para;
            dpdec[u]=dpdec[para];
        }
    }
    else{
    	dpinc[u]=u;
        dpdec[u]=u;
        high[u]=1;
    }
    timea++;
    stf[u].first=timea;
    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;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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;
            nowq++;
            allq[nowq].c=c;
            allq[nowq].u=alled[now].u;
            allq[nowq].v=alled[now].v;
            allq[nowq].w=alled[now].w;
            adj[alled[now].u].push_back(now);
            adj[alled[now].v].push_back(now);
            continue;
        }
        if(c=='Q'){
            nowq++;
            allq[nowq].c=c;
            cin>>allq[nowq].u>>allq[nowq].v;
            allq[nowq].w=now;
            continue;
        }
        nowq++;
        allq[nowq].c=c;
        cin>>allq[nowq].u;
        allq[nowq].w=now;
    }
    dfs(1);
    for(int i=1;i<=n;i++){
    	seg1.upd(1,0,kaf-1,stf[i].first,stf[i].second,make_pair(high[i],i));
    	seg2.aval(stf[i].first+kaf,stf[dpdec[i]].first);
    }
    seg2.pre();
    for(int i=1;i<=nowq;i++){
        if(allq[i].c=='S'){
        	int u=allq[i].u,v=allq[i].v;
        	if(stf[v].first<stf[u].first){
        		swap(u,v);
        	}
        	seg2.upd(stf[v].first+kaf,stf[dpdec[v]].first);
        	seg1.upd(1,0,kaf-1,stf[v].first,stf[v].second,make_pair(-high[v],v));
        	continue;
        }
        if(allq[i].c=='Q'){
        	int u=allq[i].u,v=allq[i].v;
        	swap(u,v);
        	pair<int,int> lowa=seg1.pors(kaf+stf[u].first);
        	//cout<<u<<" "<<lowa<<" 1\n";
        	if(lowa.first==0||lowa.first<high[dpinc[u]]){
        		lowa.second=dpinc[u];
        	}
        	if((stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second&&stf[v].first>=stf[lowa.second].first)){
        		cout<<"yes\n";
        		continue;
        	}
        	if(!(stf[v].first>=stf[u].first&&stf[v].second<=stf[lowa.second].second)){
        		cout<<"no\n";
        		continue;
        	}
        	int cnt=seg2.pors(1,0,kaf-1,stf[v].first,stf[v].first,stf[u].first);
        	if(cnt==1||u==v){
        		cout<<"yes\n";
        	}
        	else{
        		cout<<"no\n";
        	}
        	continue;
        }
        int u=allq[i].u;
        pair<int,int> lowa=seg1.pors(kaf+stf[u].first);
      //  cout<<u<<" "<<lowa.second<<" 1\n";
        if(lowa.first==0||lowa.first<high[dpinc[u]]){
        	lowa.second=dpinc[u];
        }
        //cout<<u<<" "<<lowa.second<<" 2\n";
        int cnt=seg2.pors(1,0,kaf-1,stf[u].first+1,stf[lowa.second].second,stf[u].first);
        //if(seg2.pors(1,0,kaf-1,stf[u].first,stf[u].first,stf[u].first)==0){
        	cnt+=high[u]-high[lowa.second]+1;
        //}
        cout<<cnt<<"\n";
    }
}

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