QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#516342#5504. Flower Gardenbai_hongTL 6ms53812kbC++143.7kb2024-08-12 16:16:392024-08-12 16:16:39

Judging History

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

  • [2024-08-12 16:16:39]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:53812kb
  • [2024-08-12 16:16:39]
  • 提交

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...

output:


result: