QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#471248 | #5504. Flower Garden | yinhee | WA | 2284ms | 123040kb | C++20 | 4.3kb | 2024-07-10 20:04:12 | 2024-07-10 20:04:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>
il void read(T &x){
int f=1;x=0;char c=gc();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=gc();
}
while(c>='0'&&c<='9'){
x=x*10+c-48,c=gc();
}
x*=f;
}
template<typename T,typename ...Args>
void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>
il void write(T x){
char buf[43];int len=0;
if(x<0){
pc('-'),x=-x;
}
do{
buf[++len]=x%10,x/=10;
}while(x);
while(len){
pc(buf[len--]+'0');
}
}
}
using namespace my_std;
const int N=1e5+7,M=1e6+7,inf=0x3f3f3f3f,mod=0;
int n,m,k,ans[M];
int cur,top,dfn[M],low[M],st[M];
bool getAns=0,vis[M];
int s,col[M],siz[M];
int tot,head[M];
struct node{
int to,nxt;
}e[M<<3];
vector<int> E[M];
il void add(int u,int v){
e[++tot]={v,head[u]},head[u]=tot;
E[v].eb(u);
}
struct SGT{
int tr[N<<2];
void build(int l,int r,int o){
if(l==r){
tr[o]=l;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
tr[o]=++k;
add(tr[o<<1],tr[o]),add(tr[o<<1|1],tr[o]);
}
void update(int l,int r,int o,int x,int y,int k){
if(l>=x&&r<=y){
add(tr[o],k);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y,k);
}
if(y>mid){
update(mid+1,r,o<<1|1,x,y,k);
}
}
}T;
struct sgt{
int tr[N<<2];
void build(int l,int r,int o){
if(l==r){
tr[o]=l;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
tr[o]=++k;
add(tr[o],tr[o<<1]),add(tr[o],tr[o<<1|1]);
}
void update(int l,int r,int o,int x,int y,int k){
if(l>=x&&r<=y){
add(k,tr[o]);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y,k);
}
if(y>mid){
update(mid+1,r,o<<1|1,x,y,k);
}
}
}R;
void tarjan(int u){
dfn[u]=low[u]=++cur;
st[++top]=u;
vis[u]=1;
go(i,u){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
s++;
do{
int v=st[top];
col[v]=s,siz[s]+=v<=n;
vis[s]=0;
}while(st[top--]!=u);
}
}
void check(int u){
rep(i,1,n*10){
ans[i]=vis[i]=0;
}
int v=0;
rep(i,1,k){
if(col[i]==u){
v=i;
break;
}
}
assert(v);
queue<int> q;
vis[v]=1,q.push(v);
while(q.size()){
int u=q.front();
q.pop();
ans[col[u]]=1;
go(i,u){
int v=e[i].to;
if(vis[v]){
continue;
}
vis[v]=1,q.push(v);
}
}
int sum=0;
rep(i,1,s){
if(ans[i]){
sum+=siz[i];
}
}
if(sum>=n/3&&sum<=n/3*2){
getAns=1;
return;
}
rep(i,1,n*10){
ans[i]=vis[i]=0;
}
while(q.size()){
q.pop();
}
v=0;
rep(i,1,k){
if(col[i]==u){
v=i;
break;
}
}
assert(v);
vis[v]=1,q.push(v);
while(q.size()){
int u=q.front();
q.pop();
ans[col[u]]=1;
for(int v:E[u]){
if(vis[v]){
continue;
}
vis[v]=1,q.push(v);
}
}
sum=0;
rep(i,1,s){
ans[i]^=1;
if(ans[i]){
sum+=siz[i];
}
}
if(sum>=n/3&&sum<=n/3*2){
getAns=1;
return;
}
}
void Yorushika(){
read(n,m),n*=3;
rep(i,1,n*10){
head[i]=dfn[i]=siz[i]=vis[i]=ans[i]=0;
E[i].clear();
}
k=n,tot=cur=s=0;
T.build(1,n,1),R.build(1,n,1);
while(m--){
int l,r,x,y;read(l,r,x,y);
k++;
T.update(1,n,1,l,r,k),R.update(1,n,1,x,y,k);
}
rep(i,1,k){
if(!dfn[i]){
tarjan(i);
}
}
int sum=0;
rep(i,1,s){
if(siz[i]>n/3*2){
puts("NIE");
return;
}
}
rep(i,1,s){
if(siz[i]>=n/3){
check(i);
if(getAns){
goto END;
}
}
}
rep(i,1,s){
sum+=siz[i],ans[i]=1;
if(sum>=n/3){
assert(sum<=n/3*2);
break;
}
}
END:
puts("TAK");
int cnt=0;
rep(i,1,n){
pc(ans[col[i]]?'F':'R');
cnt+=ans[col[i]];
}
// if(cnt<n/3||cnt>2*n/3){
// assert(0);
// }
puts("");
}
signed main(){
int t=1;
read(t);
while(t--){
Yorushika();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 24304kb
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: 0
Accepted
time: 2284ms
memory: 123040kb
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: -100
Wrong Answer
time: 1366ms
memory: 95044kb
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 FRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
result:
wrong answer odpowiedz ma za malo/duzo roz!