Submission #1009037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009037		erering	Parachute rings (IOI12_rings)	C++17	0 / 100	4042 ms	41112 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
const long long inf=1e18;
const int MOD=998244353;
const int N=1e6+5;
vector<int> adj[N];
int n;
bool vis[N];
struct info{
    int one;
    int two;
    int three;
    int mx;
};
info dfs(int node,int par){
    vis[node]=1;
    info rt; rt.one=0; rt.two=0; rt.three=0; rt.mx=adj[node].size();
    if(adj[node].size()<=1)rt.one=1;
    if(adj[node].size()==2)rt.two=1;
    if(adj[node].size()==3)rt.three=1;
    for(auto i:adj[node]){
        if(vis[i])continue;
        info s=dfs(i,node);
        rt.one+=s.one;
        rt.two+=s.two;
        rt.three+=s.three;
        rt.mx=max(rt.mx,s.mx);
    }
    return rt;
}
void dfs2(int node,int par){
    vis[node]=1;
    for(auto i:adj[node]){
        if(!vis[i])dfs2(i,node);
    }
}
void Init(int N){
 n=N;
}
void Link(int A, int B){
    adj[A].pb(B);
    adj[B].pb(A);
}
int CountCritical(){
    for(int i=1;i<=n;i++)vis[i]=0;
    info am; am.one=0; am.two=0; am.three=0; am.mx=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            info you=dfs(i,0);
            if(you.mx==0)you.one++;
            am.one+=you.one;
            am.two+=you.two;
            am.three+=you.three;
            am.mx=max(am.mx,you.mx);
        }
    }
    //cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<endl;
    if(am.mx>3)return 0;
    int ans=0;
    for(int i=1;i<=n;i++){
       // cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<endl;
        info ar=am;
        for(auto j:adj[i]){
            if(adj[j].size()==3){
                ar.three--;
                ar.two++;
            }
            else if(adj[j].size()==2){
                ar.two--;
                ar.one++;
            }
            else{
                ar.one++;
            }
        }
        if(adj[i].size()==0)ar.one-=2;
        if(adj[i].size()==1)ar.one--;
        if(adj[i].size()==2)ar.two--;
        if(adj[i].size()==3) ar.three--;
        int comp=0;
        for(int j=1;j<=n;j++)vis[j]=0;
        vis[i]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                dfs2(j,0);
                comp++;
            }
        }
      //  if(i==4)cout<<am.mx<<" "<<am.one<<" "<<am.two<<" "<<am.three<<' '<<comp<<endl;
        bool flag=1;
        if(ar.three>0)flag=0;
        if(ar.one!=comp*2)flag=0;
        if(flag)ans++;
    }
    return ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31