QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472756 | #5504. Flower Garden | yz_ly | WA | 1332ms | 96760kb | C++14 | 4.4kb | 2024-07-11 19:04:14 | 2024-07-11 19:04:15 |
Judging History
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!