QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99315#5504. Flower GardenCharlieVinnieRE 36ms192604kbC++173.6kb2023-04-21 21:28:572023-04-21 21:28:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-21 21:28:59]
  • 评测
  • 测评结果:RE
  • 用时:36ms
  • 内存:192604kb
  • [2023-04-21 21:28:57]
  • 提交

answer

#include "bits/stdc++.h"
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
using namespace std;
const int N=1e5+5,M=2e6+6; typedef long long ll;
char ans[N]; int n,m,id[2][N][20],lg2[N],tot,dfn[M],low[M],dfscnt,cnt,siz[M],st[M],ins[M],tp,q[M],h,t,vis[M],num[M],in[M]; vector<int> to[M],fo[M],lis[M],tto[M];
void dfs(int u){
    dfn[u]=low[u]=++dfscnt; st[++tp]=u; ins[u]=1;
    for(int v:to[u]){
        if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int z; lis[++cnt].clear(); siz[cnt]=0;
        do{
            z=st[tp--]; ins[z]=0; lis[cnt].push_back(z); siz[cnt]+=z<=n; num[z]=cnt;
        }while(z!=u);
    }
}
void add(int x,int y){
    to[x].push_back(y); fo[y].push_back(x);
}
void solve(){
    cin>>n>>m; n*=3;
    lg2[1]=0; For(i,2,n) lg2[i]=lg2[i>>1]+1;
    tot=n; For(o,0,1) For(j,1,lg2[n]) For(i,1,n-(1<<j)+1) id[o][i][j]=++tot;
    For(i,1,n) id[0][i][0]=id[1][i][0]=i;
    For(i,1,tot) to[i].clear(),fo[i].clear(),dfn[i]=0;
    For(j,1,lg2[n]) For(i,1,n-(1<<j)+1){
        add(id[0][i][j-1],id[0][i][j]);
        add(id[0][i+(1<<(j-1))][j-1],id[0][i][j]);
        add(id[1][i][j],id[1][i][j-1]);
        add(id[1][i][j],id[1][i+(1<<(j-1))][j-1]);
    }
    For(i,1,m){
        int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;
        int k1=lg2[r1-l1+1], k2=lg2[r2-l2+1];
        int u1=id[0][l1][k1],u2=id[0][r1-(1<<k1)+1][k1], v1=id[1][l2][k2],v2=id[1][r2-(1<<k2)+1][k2];
        to[u1].push_back(v1); to[u1].push_back(v2);
        to[u2].push_back(v1); to[u2].push_back(v2);
    }
    dfscnt=cnt=tp=0;
    For(i,1,tot) if(!dfn[i]) dfs(i);
    int Big=0; For(i,1,cnt) if(siz[i]>=n/3) { Big=i; break; }
    if(!Big){
        cerr<<"Not Big\n";
        ans[n+1]='\0'; For(i,1,n) ans[i]='F';
        For(i,1,cnt) tto[i].clear(),in[i]=0;
        For(u,1,tot) for(int v:to[u]) if(num[u]!=num[v]) tto[num[u]].push_back(num[v]),in[num[v]]++;
        h=t=0; For(i,1,cnt) if(!in[i]) q[t++]=i;
        while(h<t){
            int u=q[h++]; for(int v:tto[u]) if(!--in[v]) q[t++]=v;
        }
        assume(t==cnt-1);
        int s=0;
        For(i,0,t-1){
            int o=q[i];
            for(int u:lis[o]) if(u<=n) ans[u]='R';
            s+=siz[o]; if(s>=n/3) break;
        }
        cout<<"TAK\n";
        cout<<ans+1<<'\n';
    }
    else{
        For(i,1,tot) vis[i]=0;
        h=t=0; for(int u:lis[Big]) vis[u]=1,q[t++]=u;
        while(h<t){
            int u=q[h++];
            for(int v:to[u]) if(!vis[v]) vis[v]=1,q[t++]=v;
        }
        if(t<=n/3*2){
            cout<<"TAK\n";
            For(i,1,n) cout<<(vis[i]?"F":"R");; cout<<'\n';
            return;
        }
        For(i,1,tot) vis[i]=0;
        h=t=0; for(int u:lis[Big]) vis[u]=1,q[t++]=u;
        while(h<t){
            int u=q[h++];
            for(int v:fo[u]) if(!vis[v]) vis[v]=1,q[t++]=v;
        }
        if(t<=n/3*2){
            cout<<"TAK\n";
            For(i,1,n) cout<<(vis[i]?"R":"F");; cout<<'\n';
            return;
        }
        cout<<"NIE\n";
    }
}
signed main(){
    int T; cin>>T; while(T--) solve();
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 36ms
memory: 192604kb

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
Runtime Error

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: