本地过洛谷TLE
  • 板块学术版
  • 楼主Anonymely
  • 当前回复16
  • 已保存回复16
  • 发布时间2022/4/23 10:28
  • 上次更新2023/10/28 03:04:58
查看原帖
本地过洛谷TLE
550957
Anonymely楼主2022/4/23 10:28
#include<bits/stdc++.h>
#include <immintrin.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <type_traits>
#include <utility>
using namespace std;

#define LL long long
#define pii pair<int,int>
#define mod
#define eps
#define N 
#define mk make_pair
#define mt template<typename T>
#define newspace putchar(' ')
#define newline putchar(10)

namespace fastIO{
	mt void read(T &x){
		x=0;
		char ch=getchar();T fl=1;
		while(ch<'0'||ch>'9'){if(ch=='-')fl=-1,ch=getchar();};
		while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
		x=x*fl;
	}
	mt void readarray(T n,T a[]){
		for(int i=1;i<=n;i++)read(a[i]);
	}
	mt void write(T x){
		if(x<0){
			x=-x;putchar('-');
		}
		if(x/10)write(x/10);
		putchar(x%10+'0');
	}
	void readstr(string &s){
		char ch=getchar();
		while(ch!=' '||ch!='\n'){
			s+=ch;	
			ch=getchar();
		}
	}
	void writestr(string s){
		int i=0;
		while(i<s.length()){
			putchar(s[i]);i++;
		}
	}
}

using namespace fastIO;

namespace fastmath{
	mt T _max(T a,T b){if(a>b)return a;else return b;};
	mt T _min(T a,T b){if(a<b)return a;else return b;};
	mt T _maxpos(T a,T b){if(a==0)return b;if(b==0)return a;return _max(a,b);};
	mt T _minpos(T a,T b){if(a==0)return b;if(b==0)return a;return _min(a,b);};
	mt void _swap(T a,T b){a^=b^=a^=b;};
	mt T _sum(T siz,T a[]){
		T sum=0;
		for(int i=1;i<=siz;i++)sum+=a[i];
		return sum;
	}
	mt T _pow(T a,T b){
		T ans=1;
		for(;b;b>>=1,a=a*a){
			if(b&1)ans*=a;
		}
		return ans;
	}
	mt T _modpow(T a,T b,T md){
		T ans=1;
		for(;b;b>>=1,a=(a*a)%md){
			if(b&1)ans*=a;
		}
		return ans;
	}
	mt T _abs(T a){
		if(a<0)a=-a;
		return a;
	}
	mt T _rand(T l,T r){
		T md=r-l+1;
		T rd1=rand()%md+l;
		T rd2=rand()%md+l;
		T rd3=rand()%md+l;
		rd1=(rd1*rd2)%md+l;
		rd1=(rd1*rd3)%md+l;
		return rd1; 
	}
}

using namespace fastmath;

namespace cf{
	mt void yes(T x){
		if(x==1)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
}

using namespace cf;

struct DSU{
	#define N 200005
	int siz;
	int fa[N];
	mt DSU(T n){
		siz=n;
		for(T i=1;i<=siz;i++)fa[i]=i;
	}
	mt T find(T x){
		if(x==fa[x])return x;
		else return fa[x]=find(fa[x]);
	}
	mt void merge(T x,T y){
		T xx=find(x),yy=find(y);
		fa[xx]=yy;
	}
	mt bool judge(T x,T y){
		if(find(x)==find(y))return 1;
		else return 0;
	}
};

struct tree_array{
	#define N 200005
	int siz;
	int t[N];
	mt tree_array(T n){
		siz=n;
		for(T i=1;i<=n;i++)t[i]=0;
	}
	mt T lowbit(T x){
		return x&-x;
	}
	mt void add(T x,T k){
		for(T i=x;i<=N;i+=lowbit(i)){
			t[i]+=k;
		}
	}
	mt T query(T x){
		T ans=0;
		for(T i=x;i>=1;i-=lowbit(i)){
			ans+=t[i];
		}
		return ans;
	}
};

struct poly{
	#define N 200005
	int a[N],len;//系数和长度 
	mt poly(T siz){//初始化 
		memset(a,0,sizeof(a));
		len=siz;
	} 
	mt void input(){//读入 
		for(T i=1;i<=len;i++){
			read(a[i]);
		}
	}
	mt void output(){//输出 
		for(T i=1;i<=len;i++){
			write(a[i]);newspace;
		}
		//cout<<endl;
	}
	mt
	T operator/(T s){//除法 该式/s 
		T ans;//答案多项式 
		ans.len=len-s.len+1;//长度 
		T m1=len,m2=s.len;//复制长度 
		while(m1>=m2){//开始模拟 
			T k=a[m1]/s.a[m2];//该项系数 
			//cout<<k<<endl;
			ans.a[m1-m2+1]=k;
			for(T i=m1,j=m2;i>=1&&j>=1;i--,j--){//每一项都减 
				a[i]-=s.a[j]*k;
			}
			m1--;//被除式降幂 
		}
		return ans;//返回 
	}
};

struct segment_tree{
	#define lson(u) (u<<1)
	#define rson(u) ((u<<1)|1)
	#define md(u,v) ((u+v)>>1)
	#define N 200005
	struct tree{
		int l,r;
		int sum;
		int tag;
	}t[4*N];
	int a[N];
	mt segment_tree(){
		memset(t,0,sizeof(t));
		memset(a,0,sizeof(a));
	}
	void pushup(int u){
		t[u].sum=t[lson(u)].sum+t[rson(u)].sum;
	}

	void pushdown(int u){
		t[lson(u)].tag+=t[u].tag;
		t[rson(u)].tag+=t[u].tag;
		t[lson(u)].sum+=(t[lson(u)].r-t[lson(u)].l+1)*t[u].tag;
		t[rson(u)].sum+=(t[rson(u)].r-t[rson(u)].l+1)*t[u].tag;
		t[u].tag=0; 
	}

	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		if(l==r){
			t[p].sum=a[l];
			return ;
		}
		int mid=md(l,r);
		build(lson(p),l,mid);
		build(rson(p),mid+1,r);
		pushup(p);
	}

	void add(int p,int ll,int rr,int k){
		int l=t[p].l,r=t[p].r;
		if(ll<=l&&r<=rr){
			t[p].tag+=k;
			t[p].sum+=(r-l+1)*k;
			return ;
		}
		if(t[p].tag)pushdown(p);
		int mid=md(l,r);
		if(ll<=mid)add(lson(p),ll,rr,k);
		if(mid<rr)add(rson(p),ll,rr,k);
		pushup(p);
	}

	int query(int p,int ll,int rr){
		int l=t[p].l,r=t[p].r;
		if(ll<=l&&r<=rr){
			return t[p].sum;
		}
		if(t[p].tag)pushdown(p);
		int mid=md(l,r),ans=0;
		if(ll<=mid)ans+=query(lson(p),ll,rr);
		if(mid<rr)ans+=query(rson(p),ll,rr);
		return ans;
	}
};

struct sp{
	#define N 500005
	int n;
	struct edge{
		int to,next,del;
	}e[2*N];
	int cnt=0;
	LL head[N],vis[N],dis[N],in[N],out[N];
	void build(int siz){
		n=siz;
	}
	void cleardis(){
		cnt=0;
		memset(vis,0,sizeof(vis));
		memset(dis,0x3f,sizeof(dis));
		memset(e,0,sizeof(e));
		memset(head,0,sizeof(head));
	}
	void cleartopo(){
		cnt=0;
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
	}
	void add(int u,int v,int k){
		e[++cnt].to=v;
		e[cnt].next=head[u];
		e[cnt].del=k;
		head[u]=cnt;
	}
	void spfa(int s){
		dis[s]=0;
		queue<int> q;
		q.push(s);
		while(!q.empty()){
			int x=q.front();
			q.pop();
			vis[x]=0;
			for(int i=head[x];i;i=e[i].next){
				int v=e[i].to,k=e[i].del;
				if(dis[v]>dis[x]+k){
					dis[v]=dis[x]+k;
					if(!vis[v]){
						q.push(v);
					}
				}
			}
		}
	}
	void Dijkstra(int s){
		priority_queue<pii,vector<pii>,greater<pii> > q;
		dis[s]=0;
		q.push(mk(0,s));
		 while(q.size()){
	 		int x=q.top().second;
			q.pop();
	 		if(vis[x])continue;
	 		vis[x]=1;
	 		for(int i=head[x];i;i=e[i].next){
	 			int df=e[i].to,dd=e[i].del;
	 			if(dis[x]+dd<dis[df]){
	 				dis[df]=dis[x]+dd;
	 				q.push(mk(dis[df],df));
				}
			}
	 	}
	}
	void topo(){
		queue<int> q;
		for(int i=1;i<=n;i++)if(!in[i]){
			dis[i]=0;q.push(i);
		}
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=e[i].next){
				int v=e[i].to,k=e[i].del;
				in[v]--;
				if(dis[v]<dis[x]+k)dis[v]=dis[x]+k; 
				if(!in[v])q.push(v);
			}
		}
	}
	void dfs(int u,int father){
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(v!=father)dfs(v,u);
		}
	}
	void print(){
		for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	}
};

struct st{
	#define N 200005
	int n;
	int lg2[N],fa[N][20];
	st(int a[],int siz){
		n=siz;
		for(int i=1;i<=n;i++)fa[i][0]=a[i];
	}
	void build(){
		lg2[1]=0;
		for(int i=1;i<=N;i++)lg2[i]=lg2[i>>1]+1;
		for(int j=1;j<=lg2[n];j++){
			for(int i=1;i+(1<<(j-1))<=n;i++){
				fa[i][j]=_max(fa[i][j-1],fa[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query(int l,int r){
		int k=lg2[r-l+1];
		return _max(fa[l][k],fa[r-(1<<k)+1][k]);
	}
};

struct coor{
	int xx,yy;
	mt coor(T a,T b){
		xx=a,yy=b;
	} 
	bool operator>(const coor rhs){
		return xx>rhs.xx;
	}
	bool operator<(const coor rhs){
		return xx<rhs.xx;
	}
};


void solve(){
	int n,m,q;
	read(n),read(m),read(q); 
	DSU a(n);
	for(int i=1;i<=m;i++){
		int u,v;read(u),read(v);
		a.merge(u,v);
	}
	for(int i=1;i<=q;i++){
		int u,v;read(u);read(v);
		if(a.judge(u,v))writestr("Yes");
		else writestr("No");
		newline;
	}
}

int main(){
	int t=1;//read(t);
	while(t--){
		solve();
	}
	return 0;
}

P1551 亲戚

蒟蒻求助,本地过洛谷T

2022/4/23 10:28
加载中...