提出 #73540108

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
int n,m,k;
ll a[N],b[N],c[N];
vector<int> e[N];
bool tf[N];
int dfn[N],low[N],hgs;
int rd[N];
int id[N],scccnt;
int st[N],tt=-1;
int sz[N];
bool instack[N];

void tarjan(int u){
    dfn[u]=low[u]=++hgs;
    st[++tt]=u,instack[u]=1;
    for(auto j:e[u]){
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(instack[j]) low[u]=min(low[u],dfn[j]);
    }
    
    if(dfn[u]==low[u]){
        ++scccnt;
        int y;
        do{
            y=st[tt--];
            instack[y]=0;
            id[y]=scccnt;
            sz[scccnt]++;
        }while(y!=u);
    }
    
}


void 打卡啦摩托(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++) e[i].clear();
    {
        
        vector<a2> v;
        for(int i=1;i<=n;i++) v.push_back({a[i],i});
        sort(v.begin(),v.end(),greater<a2>());
        for(int i=1;i<n;i++){
            int u=v[i][1],uu=v[i-1][1];
            e[uu].push_back(u);
            if(v[i][0]==v[i-1][0]) e[u].push_back(uu);
        }
    }
    {
        
        vector<a2> v;
        for(int i=1;i<=n;i++) v.push_back({b[i],i});
        sort(v.begin(),v.end(),greater<a2>());
        for(int i=1;i<n;i++){
            int u=v[i][1],uu=v[i-1][1];
            e[uu].push_back(u);
            if(v[i][0]==v[i-1][0]) e[u].push_back(uu);
        }
    }
    {
        
        vector<a2> v;
        for(int i=1;i<=n;i++) v.push_back({c[i],i});
        sort(v.begin(),v.end(),greater<a2>());
        for(int i=1;i<n;i++){
            int u=v[i][1],uu=v[i-1][1];
            e[uu].push_back(u);
            if(v[i][0]==v[i-1][0]) e[u].push_back(uu);
        }
    }
    for(int i=1;i<=n;i++){
        dfn[i]=0,low[i]=0,instack[i]=0,id[i]=0,st[i]=0,sz[i]=0;
        rd[i]=0;
    }
    hgs=0,scccnt=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        for(auto j:e[i]){
            // cout<<i<<" "<<j<<endl;
            if(id[i]!=id[j])
            rd[id[j]]++;
        }
    }
    int ct=0,ctsz=0;
    for(int i=1;i<=scccnt;i++){
        if(rd[i]==0){
            ct++;
            if(ct>=2) ctsz=0;
            else ctsz=sz[i];
        }
    }
    // cout<<ct<<endl;
    cout<<ctsz<<"\n";
    
    
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        打卡啦摩托();
    }
}

提出情報

ジャッジ結果