WA on #21 求条
查看原帖
WA on #21 求条
964089
run_away楼主2024/4/2 20:01

不知为何wa了

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll mod=1e9+7,maxn=2e5+5;
struct node{ll id,a,b;}p[maxn];
ll t,n,dfn[maxn],low[maxn],tot,cnt,col[maxn];
bool vis[maxn],win[maxn];
vector<ll>son[maxn];
stack<ll>st;
inline void tarjan(ll u){
    dfn[u]=low[u]=++tot,vis[u]=1;st.push(u);
    for(auto v:son[u]){
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++cnt;
        while(st.top()!=u)col[st.top()]=cnt,vis[st.top()]=0,st.pop();
        col[u]=cnt,vis[u]=0,st.pop();
    }
}
inline void init(){
    n=read();
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(col,0,sizeof(col));
    memset(win,0,sizeof(win));
    while(!st.empty())st.pop();
    for(ll i=1;i<=n;++i)son[i].clear();
    for(ll i=1;i<=n;++i)p[i].id=i,p[i].a=read();
    for(ll i=1;i<=n;++i)p[i].b=read();
    sort(p+1,p+n+1,[](node x,node y){return x.a<y.a;});
    for(ll i=2;i<=n;++i)son[p[i].id].push_back(p[i-1].id);
    sort(p+1,p+n+1,[](node x,node y){return x.b<y.b;});
    for(ll i=2;i<=n;++i)son[p[i].id].push_back(p[i-1].id);
}
signed main(){
    t=read();
    while(t--){
        init();
        for(ll i=1;i<=n;++i)if(!dfn[i])tarjan(i);
        for(ll u=1;u<=n;++u){
            for(auto v:son[u]){
                if(col[u]!=col[v])win[col[v]]=1;
            }
        }
        for(ll i=1;i<=n;++i){
            if(win[i])putchar('0');
            else putchar('1');
        }
        puts("");
    }
    return 0;
}
2024/4/2 20:01
加载中...