QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472756#5504. Flower Gardenyz_lyWA 1332ms96760kbC++144.4kb2024-07-11 19:04:142024-07-11 19:04:15

Judging History

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

  • [2024-07-11 19:04:15]
  • 评测
  • 测评结果:WA
  • 用时:1332ms
  • 内存:96760kb
  • [2024-07-11 19:04:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(int k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
首先不难想到2-sat,然后线段树优化建图后缩点,发现建图只用考虑s[x]=1->s[y]=1的部分,其余部分不用考虑
现在相当于有一个有点权的DAG,要求把DAG分成两半使得两边的点权都在[n,2*n]之内
如果有点>2*n肯定就无解
如果有一个点>=n,那么枚举这个点和前驱还是和后继在一起就行了
否则所有点都<n,直接按拓扑序一个一个点加进去,什么时候满足要求停下就行了
*/
int t,n,q,cnt,first[2000005],num,dfn[2000005],low[2000005],co[2000005],siz[2000005],vis[2000005],l,now,id[2000005],sum,ans[2000005],d[2000005],cnt1,first1[2000005];
stack<int> s;
struct q1{
	int u,w,nex;
}a[10000005],b[10000005];
void add(int u1,int w1){
	a[++cnt]={u1,w1,first[u1]};
	first[u1]=cnt;
}
void add1(int u1,int w1){
	b[++cnt1]={u1,w1,first1[u1]};
	first1[u1]=cnt1;
}
struct node{
	void build(int k,int l,int r){
		if(l==r){
			add(k+8*n,k);
			id[l]=k;
			return ;
		}
		int mid=(l+r)>>1;
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		add(2*k,k);
		add(2*k+1,k);
		add(k+8*n,2*k+8*n);
		add(k+8*n,2*k+1+8*n);
	}
	void change(int k,int l,int r,int x,int y){
		if(l>y||r<x)
			return ;
		if(l>=x&&r<=y){
			add(k,num);
			return ;
		}
		int mid=(l+r)>>1;
		change(2*k,l,mid,x,y);
		change(2*k+1,mid+1,r,x,y);
	}
	void modify(int k,int l,int r,int x,int y){
		if(l>y||r<x)
			return ;
		if(l>=x&&r<=y){
			add(num,k+8*n);
			return ;
		}
		int mid=(l+r)>>1;
		modify(2*k,l,mid,x,y);
		modify(2*k+1,mid+1,r,x,y);
	}
}tree;
void Tarjan(int u){
	s.emplace(u);
	vis[u]=1;
	dfn[u]=low[u]=++now;
	for(int i=first[u];i;i=a[i].nex){
		if(!dfn[a[i].w]){
			Tarjan(a[i].w);
			low[u]=min(low[u],low[a[i].w]);
		}
		else if(vis[a[i].w])
			low[u]=min(low[u],dfn[a[i].w]);
	}
	if(dfn[u]==low[u]){
		co[u]=++l;
		vis[u]=0;
		while(s.top()!=u){
			co[s.top()]=l;
			vis[s.top()]=0;
			s.pop();
		}
		s.pop();
	}
}
void solve(int u){
	vis[u]=1;
	sum+=siz[u];
	for(int i=first[u];i;i=a[i].nex){
		if(!vis[a[i].w])
			solve(a[i].w);
	}
}
int main(){
	t=read();
	while(t--){
		n=read();
		q=read();
		num=16*n;
		cnt=0;
		for(int i=1;i<=num;i++){
			first[i]=dfn[i]=low[i]=vis[i]=0;
		}
		tree.build(1,1,3*n);
		while(q--){
			int x=read(),y=read(),l=read(),r=read();
			num++;
			first[num]=dfn[num]=low[num]=vis[num]=0;
			if(num>7e5)
				exit(1);
			tree.change(1,1,3*n,x,y);
			tree.modify(1,1,3*n,l,r);
		}
		now=l=0;
		for(int i=1;i<=num;i++){
			if(!dfn[i])
				Tarjan(i);
		}
		for(int i=1;i<=l;i++){
			siz[i]=0;
		}
		for(int i=1;i<=3*n;i++){
			siz[co[id[i]]]++;
		}
		int flag=0;
		for(int i=1;i<=l;i++){
			if(siz[i]>2*n){
				flag=1;
				break;
			}
		}
		if(flag){
			puts("NIE");
			continue;
		}
		int all=cnt;
		cnt=cnt1=0;
		for(int i=1;i<=num;i++){
			first[i]=first1[i]=d[i]=0;
		}
		for(int i=1;i<=all;i++){
			if(co[a[i].u]!=co[a[i].w]){
				add(co[a[i].u],co[a[i].w]);
				add1(co[a[i].w],co[a[i].u]);
				d[co[a[i].u]]++;
			}
		}
		int id1=0;
		for(int i=1;i<=l;i++){
			vis[i]=0;
			if(siz[i]>=n)
				id1=i;
		}
		sum=0;
		if(id1){
			solve(id1);
			vis[id1]=0;
			sum-=siz[id1];
			if(sum>=n){
				for(int i=1;i<=3*n;i++){
					if(vis[co[id[i]]])
						ans[i]=1;
					else
						ans[i]=0;
				}
			}
			else if(siz[id1]+sum<=2*n){
				for(int i=1;i<=3*n;i++){
					if(vis[co[id[i]]]||co[id[i]]==id1)
						ans[i]=1;
					else
						ans[i]=0;
				}
			}
			else{
				puts("NIE");
				continue;
			}
		}
		else{
			queue<int> p;
			for(int i=1;i<=l;i++){
				if(!d[i])
					p.emplace(i);
			}
			while(!p.empty()){
				int k=p.front();
				p.pop();
				sum+=siz[k];
				vis[k]=1;
				if(sum>=n)
					break;
				for(int i=first1[k];i;i=b[i].nex){
					if(!(--d[b[i].w]))
						p.emplace(b[i].w);
				}
			}
			for(int i=1;i<=3*n;i++){
				if(vis[co[id[i]]])
					ans[i]=1;
				else
					ans[i]=0;
			}
		}
		puts("TAK");
		for(int i=1;i<=3*n;i++){
			putchar(ans[i]?'F':'R');
		}
		putchar('\n');
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 25992kb

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
RFF
NIE

result:

ok good!

Test #2:

score: 0
Accepted
time: 1332ms
memory: 96760kb

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:

NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE
NIE

result:

ok good!

Test #3:

score: 0
Accepted
time: 913ms
memory: 89396kb

input:

10
33333 100000
15207 33614 66276 66276
97173 97173 67589 73960
19673 36626 65207 65207
89825 98169 27079 27079
56067 56966 7560 7560
18170 35477 18752 18752
32621 36748 34460 34460
61595 61700 14117 14117
32395 36710 9064 9064
13172 13172 1728 4640
40462 41878 47171 47171
76965 82414 5767 5767
9225...

output:

TAK
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

result:

ok good!

Test #4:

score: 0
Accepted
time: 910ms
memory: 85464kb

input:

10
33333 100000
2646 2646 6430 6446
82226 82231 15128 15132
877 877 85831 88474
51389 79196 37573 37573
38030 38030 14248 14280
63032 68489 81074 81074
46468 46468 7403 7487
19864 20058 97979 97979
71640 71833 8558 8558
12121 12434 82481 82481
32901 32901 1899 2162
65312 77886 75969 75974
87983 8798...

output:

TAK
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFRRFFFFRFFRRFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

result:

ok good!

Test #5:

score: -100
Wrong Answer
time: 246ms
memory: 26292kb

input:

87005
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
1 1
1 3 2 3
1 2
1 1 2 2
2 2 1 1
1 2
1 3 1 1
1 1 1 3
4 20
3 5 6 12
4 5 7 11
1 1 2 2
3 4 7 12
3 5 10 10
3 5 8 8
4 4 9 11
4 4 7 7
1 1 9 10
3 4 6 9
3 5 11 12
3 3 7 9
3 5 2 2
4 5 2 2
1 1 7 11
1 1 10 10
3 5 7 8
4 4 2 2
1 1 2 2
4 5 8 10
4 12
11 ...

output:

TAK
RFF
NIE
TAK
RFF
TAK
FFR
NIE
TAK
RRFRRRFFRRFR
TAK
RRRFFRRRFRRF
NIE
TAK
RFRRFFRFRRFRRRR
TAK
RRFRRFRRRFRF
TAK
RFFRRFFRRRRR
TAK
FRRRRRRRFFRFFRR
TAK
RRFRRRFRFRRF
TAK
RRRFFRFRRFFRRRR
NIE
TAK
RRFFRRRFRFRR
NIE
TAK
RRFFFRRFF
NIE
TAK
RRFFFRRRR
TAK
FFRRRRRRFRRF
TAK
RRFFRFRFFFFFRFF
TAK
FFFRRRRRRRRF
NIE
TAK
...

result:

wrong answer odpowiedz nie spelnia wymogow!