QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#98992 | #5504. Flower Garden | AFewSuns | WA | 2579ms | 130952kb | C++14 | 4.1kb | 2023-04-21 08:00:57 | 2023-04-21 08:01:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
vector<ll> vec[1000010];
ll t,n,q,head[1000010],cnt=0,tot=0;
ll dfn[1000010],low[1000010],tott=0,blg[1000010],cntt=0,st[1000010],top=0;
ll id[1000010],mp[1000010],num=0,siz[1000010],in[1000010];
bl ck[1000010];
struct node{
ll nxt,to;
}e[5000050];
void add(ll u,ll v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
struct seg{
#define LC lc[x]
#define RC rc[x]
ll rt,lc[400040],rc[400040];
il void pushup(ll x,bl o){
if(!o){
add(LC,x);
add(RC,x);
}
else{
add(x,LC);
add(x,RC);
}
}
void build(ll &x,ll l,ll r,bl o){
x=++tot;
if(l==r){
if(!o) add(l,x);
else add(x,l);
return;
}
ll mid=(l+r)>>1;
build(LC,l,mid,o);
build(RC,mid+1,r,o);
pushup(x,o);
}
void mdf(ll x,ll l,ll r,ll ql,ll qr,ll v,bl o){
if(ql<=l&&r<=qr){
if(!o) add(x,v);
else add(v,x);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid) mdf(LC,l,mid,ql,qr,v,o);
else mdf(RC,mid+1,r,ql,qr,v,o);
}
}up,dwn;
void tarjan(ll u){
dfn[u]=low[u]=++tott;
st[++top]=u;
ck[u]=1;
go(u){
ll v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ck[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
blg[u]=++cntt;
ck[u]=0;
while(st[top]!=u){
blg[st[top]]=cntt;
ck[st[top]]=0;
top--;
}
top--;
}
}
void topo(){
queue<ll> Q;
fr(i,1,cntt) if(!in[i]) Q.push(i);
while(!Q.empty()){
ll u=Q.front();
Q.pop();
id[++num]=u;
fr(i,0,(ll)vec[u].size()-1){
ll v=vec[u][i];
in[v]--;
if(!in[v]) Q.push(v);
}
}
}
void dfs(ll u){
ck[u]=1;
fr(i,0,(ll)vec[u].size()-1){
ll v=vec[u][i];
if(!ck[v]) dfs(v);
}
}
void clr(){
fr(i,1,tot) head[i]=dfn[i]=low[i]=blg[i]=ck[i]=0;
fr(i,1,cntt){
vec[i].clear();
in[i]=siz[i]=0;
}
cnt=tot=tott=cntt=0;
}
int main(){
t=read();
while(t--){
n=read();
q=read();
tot=3*n;
up.build(up.rt,1,3*n,0);
dwn.build(dwn.rt,1,3*n,1);
while(q--){
ll l1=read(),r1=read(),l2=read(),r2=read();
tot++;
up.mdf(up.rt,1,3*n,l1,r1,tot,0);
dwn.mdf(dwn.rt,1,3*n,l2,r2,tot,1);
}
fr(i,1,tot) if(!dfn[i]) tarjan(i);
fr(u,1,tot){
if(u<=3*n) siz[blg[u]]++;
go(u){
ll v=e[i].to;
if(blg[u]==blg[v]) continue;
vec[blg[u]].push_back(blg[v]);
in[blg[v]]++;
}
}
topo();
ll now=0,pos=0;
fr(i,1,cntt){
now+=siz[i];
if(now>=n&&now<=2*n) pos=i;
}
if(pos){
fr(i,1,cntt) mp[id[i]]=i;
pf("TAK\n");
fr(i,1,3*n){
if(mp[blg[i]]<=pos) pc('R');
else pc('F');
}
enter;
}
else{
fr(i,1,cntt) if(siz[i]>=n) pos=i;
dfs(pos);
ll sum=0;
fr(i,1,cntt) if(ck[i]) sum+=siz[i];
if(sum>2*n) pf("NIE\n");
else{
pf("TAK\n");
fr(i,1,3*n){
if(ck[blg[i]]) pc('R');
else pc('F');
}
enter;
}
}
clr();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 28596kb
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: 1346ms
memory: 87896kb
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: 2579ms
memory: 130952kb
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:
wrong answer odpowiedz nie spelnia wymogow!