QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#77850 | #5504. Flower Garden | 18Michael | WA | 7ms | 62864kb | C++14 | 5.5kb | 2023-02-15 18:42:38 | 2023-02-15 18:42:41 |
Judging History
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!