QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77850#5504. Flower Garden18MichaelWA 7ms62864kbC++145.5kb2023-02-15 18:42:382023-02-15 18:42:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-15 18:42:41]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:62864kb
  • [2023-02-15 18:42:38]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
const int MxV=1200002,MxE=50000002,MxN=100002,MxQ=100002;
int n,n2,n3,q,t,edge_t,dfn_t,st_t,rt_t,s,s2,cnt,e_t,Test_num;
bool Ok;
int a[MxQ],b[MxQ],c[MxQ],d[MxQ],lson[MxV],rson[MxV],val[MxV],la[MxV],num[MxN],dfn[MxV],low[MxV],rt[MxV],st[MxV],sum[MxV],lae[MxV],from[MxE],deg[MxV];
bool ok[MxV],ins[MxV],u[MxV];
vector<int> vec,vec1;
vector<int> vec2[MxV];
queue<int> Q,ept;
struct aaa
{
	int to,nx;
}edge[MxE],e[MxE];
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x=f? -x:x;return ;
}
inline void add_edge(int x,int y)
{
	//printf("      ADD %d %d\n",x,y);
	edge[++edge_t]=(aaa){y,la[x]},la[from[edge_t]=x]=edge_t;
}
inline void add_e(int x,int y)
{
	//printf("      add_e %d(%d) %d(%d)\n",x,sum[x],y,sum[y]);
	if(x^y)e[++e_t]=(aaa){y,lae[x]},++deg[y],lae[x]=e_t;
}
inline int newnode()
{
	return ++t,la[t]=val[t]=dfn[t]=rt[t]=0,t;
}
inline void build(int k,int l,int r)
{
	//if(l==r)printf("num[%d]=%d\n",l,k);
	if(l==r)return (void)(val[num[l]=k]=1);
	int mid=((l+r)>>1);
	build(lson[k]=newnode(),l,mid),build(rson[k]=newnode(),mid+1,r),add_edge(k,lson[k]),add_edge(k,rson[k]);
}
inline void build2(int k,int l,int r)
{
	if(l==r)return ;
	int mid=((l+r)>>1);
	build2(lson[k]=(l==mid? num[l]:newnode()),l,mid),build2(rson[k]=(mid+1==r? num[r]:newnode()),mid+1,r),add_edge(lson[k],k),add_edge(rson[k],k);
}
inline void add(int k,int l,int r,int l1,int r1,int x)
{
	if(l>=l1 && r<=r1)return add_edge(x,k);
	int mid=((l+r)>>1);
	if(l1<=mid)add(lson[k],l,mid,l1,r1,x);
	if(r1>mid)add(rson[k],mid+1,r,l1,r1,x);
}
inline void add2(int k,int l,int r,int l1,int r1,int x)
{
	if(l>=l1 && r<=r1)return add_edge(k,x);
	int mid=((l+r)>>1);
	if(l1<=mid)add2(lson[k],l,mid,l1,r1,x);
	if(r1>mid)add2(rson[k],mid+1,r,l1,r1,x);
}
inline void Tarjan(int x)
{
	dfn[x]=low[x]=(++dfn_t),ins[st[++st_t]=x]=1;
	for(int i=la[x],v;i;i=edge[i].nx)
	{
		v=edge[i].to;
		if(!dfn[v])Tarjan(v),low[x]=min(low[x],low[v]);
		else if(ins[v])low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x])for(sum[++rt_t]=0,vec2[rt_t].clear();st[st_t+1]!=x;--st_t)rt[st[st_t]]=rt_t,sum[rt_t]+=val[st[st_t]],vec2[rt_t].push_back(st[st_t]),ins[st[st_t]]=0;
}
inline void print()
{
	Ok=1,puts("TAK");
	for(int i=1;i<=n3;++i)putchar(u[num[i]]? 'R':'F');
	puts("");
}
inline void solve1()
{
	//cerr<<"solve1\n";
	e_t=0,cnt=n3,Q=ept;
	for(int i=1;i<=rt_t;++i)lae[i]=deg[i]=0;
	for(int i=1;i<=edge_t;++i)add_e(rt[from[i]],rt[edge[i].to]);
	for(int i=1;i<=rt_t;++i)if(!deg[i])Q.push(i),ins[i]=1;else ins[i]=0;
	for(int i=1;i<=t;++i)u[i]=0;
	for(int p;Q.size();)
	{
		p=Q.front(),Q.pop(),cnt-=sum[p];
		//printf("p:%d sum:%d cnt:%d\n",p,sum[p],cnt);
		for(int i=0;i<vec2[p].size();++i)u[vec2[p][i]]=1/*,printf(" u[%d]=1\n",vec2[p][i])*/;
		//for(int i=1;i<=n3;++i)printf("%d%c",u[num[i]],i==n3? '\n':' ');
		if(cnt>=n && cnt<=n2)return print();
		for(int i=lae[p],v;i;i=e[i].nx)if(!(--deg[v=e[i].to]) && !ins[v])Q.push(v),ins[v]=1;
	}
	puts("FAIL");
}
inline void dfs(int x)
{
	//printf("DFS %d\n",x);
	ins[x]=1,cnt-=sum[x];
	for(int i=0;i<vec2[x].size();++i)u[vec2[x][i]]=1;
	for(int i=lae[x],v;i;i=e[i].nx)if(!ins[v=e[i].to])dfs(v);
}
inline void solve3()
{
	//cerr<<"solve3\n";
	for(int i=1;i<=t;++i)u[i]=0;
	cnt=n3,e_t=0,Q=ept;
	for(int i=1;i<=rt_t;++i)lae[i]=ins[i]=0;
	for(int i=1;i<=edge_t;++i)add_e(rt[edge[i].to],rt[from[i]]);
	//printf("vec1:");for(int i=0;i<vec1.size();++i)printf(" %d",vec1[i]);puts("");
	//printf("bef u:");for(int i=1;i<=t;++i)printf("%d%c",u[i],i==t? '\n':' ');
	for(int i=0;i<vec1.size();++i)dfs(vec1[i]);
	//puts(" ================");
	cnt=n3,e_t=0;
	for(int i=1;i<=rt_t;++i)lae[i]=deg[i]=0;
	//printf("aft u:");for(int i=1;i<=t;++i)printf("%d%c",u[i],i==t? '\n':' ');
	for(int i=1;i<=edge_t;++i)if(!u[from[i]] && !u[edge[i].to])add_e(rt[from[i]],rt[edge[i].to]);
	for(int i=1;i<=rt_t;++i)if(!u[vec2[i][0]] && !ok[i] && !deg[i])Q.push(i),ins[i]=1;else ins[i]=0;
	for(int p;Q.size();)
	{
		p=Q.front(),Q.pop(),cnt-=sum[p];
		//printf("p:%d sum:%d cnt:%d\n",p,sum[p],cnt);
		for(int i=0;i<vec2[p].size();++i)u[vec2[p][i]]=1/*,printf(" u[%d]=1\n",vec2[p][i])*/;
		//for(int i=1;i<=n3;++i)printf("%d%c",u[num[i]],i==n3? '\n':' ');
		if(cnt>=n && cnt<=n2)return print();
		for(int i=lae[p],v;i;i=e[i].nx)if(!(--deg[v=e[i].to]) && !ok[v] && !ins[v])Q.push(v),ins[v]=1;
	}
}
inline void solve2()
{
	//cerr<<"solve2\n";
	vec1.clear();
	for(int i=0;i<vec.size();++i)vec1.push_back(vec[i]);
	if(solve3(),Ok)return ;
	for(int i=0;i<vec.size();++i)
	{
		for(int j=1;j<=t;++j)u[j]=0;
		vec1.clear(),ok[vec[i]]=1;
		if(vec.size()>1)vec1.push_back(vec[i^1]);
		solve3(),ok[vec[i]]=0;
		if(Ok)return ;
	}
	puts("NIE");
}
inline void solve()
{
	read(n),read(q),n2=(n<<1),n3=n*3,edge_t=dfn_t=rt_t=t=Ok=0,vec.clear(),build(s=newnode(),1,n3),/*puts(""),*/build2(s2=newnode(),1,n3);
	for(int i=1;i<=q;++i)read(a[i]),read(b[i]),read(c[i]),read(d[i]),add(s,1,n3,a[i],b[i],newnode()),add2(s2,1,n3,c[i],d[i],t);
	for(int i=1;i<=t;++i)if(!dfn[i])Tarjan(i);
	/*for(int i=1;i<=rt_t;++i)
	{
		printf(" %d(%d):",i,sum[i]);
		for(int j=0;j<vec2[i].size();++j)printf("%d%c",vec2[i][j],j+1==vec2[i].size()? '\n':' ');
	}*/
	for(int i=1;i<=rt_t;++i)if(sum[i]>n)vec.push_back(i);
	if(!vec.size())solve1();
	else solve2();
}
int main()
{
	read(Test_num);
	while(Test_num--)solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 62864kb

input:

2
1 3
1 1 2 2
1 2 3 3
1 1 3 3
1 3
1 1 2 2
2 2 3 3
3 3 1 1

output:

TAK
FFR
NIE

result:

wrong answer odpowiedz nie spelnia wymogow!