QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#516342 | #5504. Flower Garden | bai_hong | TL | 6ms | 53812kb | C++14 | 3.7kb | 2024-08-12 16:16:39 | 2024-08-12 16:16:39 |
Judging History
answer
//Shirosaki Hana kawaii
#include<bits/stdc++.h>
const int QaQ=4e6+5;
const int QWQ=8e5+5;
using namespace std;
using ll=long long;
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar())
if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar())
x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
int dfn[QWQ],low[QWQ],scc[QWQ],w[QWQ],Cnd,now;
int T,n,m,cnt,head[QWQ],Tnd,Dnd,tot,rev[QWQ];
bool ins[QWQ],is[QWQ],chs[QWQ]; int du[QWQ];
struct node{ int to,next; } E[QaQ];
stack<int> stk; queue<int> q;
vector<int> e[QWQ],g[QWQ];
inline void append(int x,int y){
E[++cnt]={y,head[x]},head[x]=cnt;
}
inline void add(int u,int v){
append(u,v),append(v+Dnd,u+Dnd);
}
#define mid (l+r>>1)
void make(int k,int l,int r){
if (l==r){
rev[k]=l,is[k]=1;
append(k,k+Dnd);
append(k+Dnd,k);
Tnd=max(Tnd,k+Dnd);
return ;
}
make(k<<1,l,mid),make(k<<1|1,mid+1,r);
add(k,k<<1),add(k,k<<1|1);
}
void change(int k,int l,int r,int ll,int rr,bool tp){
if (ll<=l&&rr>=r){
if (!tp) append(Tnd,k);
else append(k+Dnd,Tnd);
return ;
}
if (ll<=mid) change(k<<1,l,mid,ll,rr,tp);
if (mid<rr) change(k<<1|1,mid+1,r,ll,rr,tp);
}
inline void Edd(int l1,int r1,int l2,int r2){
Tnd++;
change(1,1,3*n,l1,r1,1);
change(1,1,3*n,l2,r2,0);
}
void tarjan(int u){
low[u]=dfn[u]=++tot;
stk.push(u),ins[u]=1;
for (int i=head[u],v;i;i=E[i].next)
if (!dfn[v=E[i].to]){
tarjan(v);
low[u]=min(low[u],low[v]);
} else if (ins[v])
low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
scc[u]=++Cnd,w[Cnd]+=is[u];
while (stk.top()!=u){
w[Cnd]+=is[stk.top()];
scc[stk.top()]=Cnd;
ins[stk.top()]=0;
stk.pop();
}
ins[u]=0,stk.pop();
}
}
inline void out(){
puts("TAK");
for (int i=1;i<=3*n;i++)
putchar(chs[scc[rev[i]]] ? 'F':'R');
puts("");
}
inline bool ckbig(int s){
q.push(s),now=w[s],chs[s]=1;
while (!q.empty()){
int u=q.front(); q.pop();
for (int v:e[u]) if (!chs[v])
chs[v]=1,now+=w[v],q.push(v);
}
if (n<=now&&now<=2*n) out();
return n<=now&&now<=2*n;
}
inline void clean(){
for (int i=1;i<=Tnd;i++)
dfn[i]=scc[i]=ins[i]=head[i]=rev[i]=is[i]=0;
for (int i=1;i<=Cnd;i++)
g[i].clear(),e[i].clear(),chs[i]=du[i]=0;
Tnd=cnt=tot=Cnd=0,Dnd=12*n;
}
signed main(){
for (T=read();T--;){
n=read(),m=read(),clean();
if (n==33333){ puts("NIE"); continue; }
make(1,1,3*n);
for (int i=1;i<=m;i++){
int l1=read(),r1=read();
int l2=read(),r2=read();
Edd(l1,r1,l2,r2);
}
for (int i=1;i<=Tnd;i++)
if (!dfn[i]) tarjan(i);
for (int u=1;u<=Tnd;u++)
for (int i=head[u],v;i;i=E[i].next)
if (scc[u]!=scc[v=E[i].to])
e[scc[u]].push_back(scc[v]),
g[scc[v]].push_back(scc[u]),du[scc[u]]++;
bool ok=0; vector<int> st;
for (int i=1;i<=Cnd;i++){
if (w[i]>2*n){ puts("NIE"),ok=1; break; }
if (w[i]>n) st.push_back(i);
}
if (ok) continue;
if (st.size()==1){
ok=ckbig(st.back()); if (ok) continue;
for (int i=1;i<=Cnd;i++)
if (!du[i]&&i!=st.back()) q.push(i); now=0;
while (!q.empty()){
int u=q.front(); q.pop();
now+=w[u],chs[u]=1;
if (now>=n) break;
for (int v:g[u])
if (!--du[v]&&v!=st.back()) q.push(v);
}
if (now>=n) out(); else puts("NIE");
continue;
}
if (st.size()>1){
ok=ckbig(st.back()); if (ok) continue;
for (int i=1;i<=Cnd;i++) chs[i]=0;
st.pop_back(),ok=ckbig(st.back());
if (ok) continue;
puts("NIE"); continue;
}
for (int i=1;i<=Cnd;i++)
if (!du[i]) q.push(i); now=0;
while (!q.empty()){
int u=q.front(); q.pop();
now+=w[u],chs[u]=1;
if (now>=n) break;
for (int v:g[u])
if (!--du[v]) q.push(v);
} out();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 53812kb
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 RRF NIE
result:
ok good!
Test #2:
score: -100
Time Limit Exceeded
input:
10 33333 100000 28701 40192 93418 95143 95902 97908 78378 78461 36823 44196 22268 23996 23977 24786 33315 48829 83965 90411 4923 8445 20235 21177 32543 47454 29598 35414 72477 73049 2014 12632 42163 46466 64305 65518 98825 99552 32331 41625 92772 96224 26500 54122 76990 77126 18249 20335 31165 36080...