P4171 一个诡异的问题
  • 板块灌水区
  • 楼主TMLY114514
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/21 21:01
  • 上次更新2024/6/22 09:09:39
查看原帖
P4171 一个诡异的问题
1121439
TMLY114514楼主2024/6/21 21:01

为什么用 fwrite 的答案会判错，但是下点本地测没问题，换成puts就过了

WA on #10 :

#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define ll long long
#define ischar(ch) (32<ch&&ch<127)
#define SIZE 1<<18
	char ibuf[SIZE],*is=ibuf,*it=ibuf;
#define getchar() (is==it&&(it=(is=ibuf)+fread(ibuf,1,SIZE,stdin),is==it)?EOF:*is++)
	template<typename Type>
	inline void read(Type &a){
		Type x=0;int y=0,ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))y|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		a=y?-x:x;
	}
	inline void read(char &a){
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		a=ch;
	}
	inline void read(string &a){
		a="";char ch;
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))a+=ch,ch=getchar();
	}
	inline void read(short &a){
		int ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))ch=getchar();
		a=(ch^48);
	}
	template<typename Type>
	inline void read(Type a[]){
		Type *pos=a;
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))*pos++=ch,ch=getchar();
		*pos=0;
	}
	inline void read(double &a){
		int zh=0,w=0,ch=getchar();
		double xi=0.0,x=1.0;
		while (!isdigit(ch)&&(ch^EOF))w|=ch=='-',ch=getchar();
		while(isdigit(ch))zh=(zh<<1)+(zh<<3)+(ch^48),ch=getchar();
		if(ch^'.')return void(a=w?-zh:zh);
		ch=getchar();
		while(isdigit(ch))x*=10.0,xi+=(ch^48)*1.0/x,ch=getchar();
		a=w?-zh-xi:zh+xi;
	}
	template<typename Type,typename ...Args>
	inline void read(Type &a,Args &...as){read(a);read(as...);}
	char obuf[SIZE],*op=obuf;
	inline void putch(const char &c){
		if(op-obuf==SIZE)fwrite(obuf,1,op-obuf,stdout),op=obuf;
		*op++=c;
	}
	template<typename Type>
	inline void write(Type x){
		if(x<0)putch('-'),x=-x;
		static int s[35],top;top=0;
		do s[top++]=x%10,x/=10;
		while(x);
		while(top)putch(s[--top]+'0');
	}
	int precision;
	inline void write(double x){
		ll n=1,base=10,k=precision;
		while(k)n=(k&1)?n*base:n,base*=base,k>>=1;
		x=round(x*n)/n;
		if(!x){
			putch('0'),putch('.');
			for(int i=1;i<=precision;++i)putch('0');
			return;
		}
		if(x<0)putch('-'),x=-x;
		ll y=(ll)round(x*n)%n;x=(ll)x;
		write((ll)x);putch('.');
		int s[35],top=0;
		for(;top<precision;y/=10)s[++top]=y%10;
		while(top)putch(s[top--]+'0');
	}
	inline void write(char ch){putch(ch);}
	inline void write(string s){for(int i=0;i<s.size();++i)putch(s[i]);}
	template<typename Type,typename ...Args>
	inline void write(Type a,Args ...as){write(a);write(as...);}
	inline void oclear(){fwrite(obuf,1,op-obuf,stdout);}
#undef SIZE
#undef ischar
}
using namespace IO;
#define N 210
//建边:!a->b !b->a
//同一个强连通分量中，变量的取值一定相同
int n,m,low[N],dfn[N],vis[N],num,rt[N],tot,st[N],top;
vector<int>e[N];
#define add(u,v) e[u].push_back(v)
inline void tarjan(int u){
	low[u]=dfn[u]=++num;
	vis[st[++top]=u]=1;
	for(int v:e[u])
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
	else if(vis[v])low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u]){
		++tot;
		while(st[top]^u)vis[st[top]]=0,rt[st[top--]]=tot;
		vis[u]=0;rt[st[top--]]=tot;
	}
}//rt[i]存的是这一组强连通分量的逆拓扑序
//取强连通分量里编号小的，因为拓扑序靠前，所以优先满足
inline int get(string s){
	int x=0;
	for(int i=1;i<s.size();++i)x=(x<<1)+(x<<3)+(s[i]^48);
	return x;
}
int t;
int main(){
	read(t);
	while(t--){
		tot=top=num=0;
		memset(rt,0,sizeof rt);
		memset(dfn,0,sizeof dfn);
		memset(vis,0,sizeof vis);
		read(n,m);
		for(int i=1;i<=n<<1;++i)e[i].resize(0);
		string s1,s2;
		for(int i=1,u,v,a,b;i<=m;++i){
			read(s1,s2);
			a=s1[0]=='m';
			b=s2[0]=='m';
			u=get(s1);
			v=get(s2);
			add(u+a*n,v+(b^1)*n),add(v+b*n,u+(a^1)*n);
		}
		for(int i=1;i<=n<<1;++i)if(!dfn[i])tarjan(i);
		int flag=1;
		for(int i=1;i<=n;++i)if(rt[i]==rt[i+n])flag=0;
		if(flag)write((string)"GOOD\n");
		else write((string)"BAD\n");
	}
	oclear();
	return 0;
}

AC :

#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define ll long long
#define ischar(ch) (32<ch&&ch<127)
#define SIZE 1<<18
	char ibuf[SIZE],*is=ibuf,*it=ibuf;
#define getchar() (is==it&&(it=(is=ibuf)+fread(ibuf,1,SIZE,stdin),is==it)?EOF:*is++)
	template<typename Type>
	inline void read(Type &a){
		Type x=0;int y=0,ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))y|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		a=y?-x:x;
	}
	inline void read(char &a){
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		a=ch;
	}
	inline void read(string &a){
		a="";char ch;
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))a+=ch,ch=getchar();
	}
	inline void read(short &a){
		int ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))ch=getchar();
		a=(ch^48);
	}
	template<typename Type>
	inline void read(Type a[]){
		Type *pos=a;
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))*pos++=ch,ch=getchar();
		*pos=0;
	}
	inline void read(double &a){
		int zh=0,w=0,ch=getchar();
		double xi=0.0,x=1.0;
		while (!isdigit(ch)&&(ch^EOF))w|=ch=='-',ch=getchar();
		while(isdigit(ch))zh=(zh<<1)+(zh<<3)+(ch^48),ch=getchar();
		if(ch^'.')return void(a=w?-zh:zh);
		ch=getchar();
		while(isdigit(ch))x*=10.0,xi+=(ch^48)*1.0/x,ch=getchar();
		a=w?-zh-xi:zh+xi;
	}
	template<typename Type,typename ...Args>
	inline void read(Type &a,Args &...as){read(a);read(as...);}
	char obuf[SIZE],*op=obuf;
	inline void putch(const char &c){
		if(op-obuf==SIZE)fwrite(obuf,1,op-obuf,stdout),op=obuf;
		*op++=c;
	}
	template<typename Type>
	inline void write(Type x){
		if(x<0)putch('-'),x=-x;
		static int s[35],top;top=0;
		do s[top++]=x%10,x/=10;
		while(x);
		while(top)putch(s[--top]+'0');
	}
	int precision;
	inline void write(double x){
		ll n=1,base=10,k=precision;
		while(k)n=(k&1)?n*base:n,base*=base,k>>=1;
		x=round(x*n)/n;
		if(!x){
			putch('0'),putch('.');
			for(int i=1;i<=precision;++i)putch('0');
			return;
		}
		if(x<0)putch('-'),x=-x;
		ll y=(ll)round(x*n)%n;x=(ll)x;
		write((ll)x);putch('.');
		int s[35],top=0;
		for(;top<precision;y/=10)s[++top]=y%10;
		while(top)putch(s[top--]+'0');
	}
	inline void write(char ch){putch(ch);}
	inline void write(string s){for(int i=0;i<s.size();++i)putch(s[i]);}
	template<typename Type,typename ...Args>
	inline void write(Type a,Args ...as){write(a);write(as...);}
	inline void oclear(){fwrite(obuf,1,op-obuf,stdout);}
#undef SIZE
#undef ischar
}
using namespace IO;
#define N 210
//建边:!a->b !b->a
//同一个强连通分量中，变量的取值一定相同
int n,m,low[N],dfn[N],vis[N],num,rt[N],tot,st[N],top;
vector<int>e[N];
#define add(u,v) e[u].push_back(v)
inline void tarjan(int u){
	low[u]=dfn[u]=++num;
	vis[st[++top]=u]=1;
	for(int v:e[u])
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
	else if(vis[v])low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u]){
		++tot;
		while(st[top]^u)vis[st[top]]=0,rt[st[top--]]=tot;
		vis[u]=0;rt[st[top--]]=tot;
	}
}//rt[i]存的是这一组强连通分量的逆拓扑序
//取强连通分量里编号小的，因为拓扑序靠前，所以优先满足
inline int get(string s){
	int x=0;
	for(int i=1;i<s.size();++i)x=(x<<1)+(x<<3)+(s[i]^48);
	return x;
}
int t;
int main(){
	read(t);
	while(t--){
		tot=top=num=0;
		memset(rt,0,sizeof rt);
		memset(dfn,0,sizeof dfn);
		memset(vis,0,sizeof vis);
		read(n,m);
		for(int i=1;i<=n<<1;++i)e[i].resize(0);
		string s1,s2;
		for(int i=1,u,v,a,b;i<=m;++i){
			read(s1,s2);
			a=s1[0]=='m';
			b=s2[0]=='m';
			u=get(s1);
			v=get(s2);
			add(u+a*n,v+(b^1)*n),add(v+b*n,u+(a^1)*n);
		}
		for(int i=1;i<=n<<1;++i)if(!dfn[i])tarjan(i);
		int flag=1;
		for(int i=1;i<=n;++i)if(rt[i]==rt[i+n])flag=0;
		if(flag)puts("GOOD");
		else puts("BAD");
	}
	return 0;
}
2024/6/21 21:01