Submission #908073

#	Time	Username	Problem	Language	Result	Execution time	Memory
908073		JakobZorz	Parachute rings (IOI12_rings)	C++17	37 / 100	1284 ms	135084 KiB

rings

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

int n;
vector<int>nodes[(int)1e6];
unordered_set<int>num3;
int num4=-1;
int num3n[(int)1e6];
int num_cycles;
unordered_set<int>cycle;

int dsu_parent[(int)1e6];
int dsu_get(int a){
    if(dsu_parent[a]<0)
        return a;
    return dsu_parent[a]=dsu_get(dsu_parent[a]);
}

void dsu_merge(int a,int b){
    a=dsu_get(a);
    b=dsu_get(b);
    if(a==b)
        return;
    if(dsu_parent[a]>dsu_parent[b])
        swap(a,b);
    dsu_parent[a]+=dsu_parent[b];
    dsu_parent[b]=a;
}

void Init(int N){
    n=N;
    for(int i=0;i<1e6;i++)
        dsu_parent[i]=-1;
}

int cvis;
int vis[(int)1e6];
int dfs(int node,int d,int end){ // -1 = dead end
    int pv=vis[node];
    vis[node]=cvis;
    
    for(int ne:nodes[node]){
        if(ne==end&&d>1)
            return end;
        if(vis[ne]!=cvis&&vis[ne]!=0)
            return ne;
            
        if(vis[ne]==0){
            int r=dfs(ne,d+1,end);
            if(r!=-1)
                return r;
        }
    }
    
    vis[node]=pv;
    return -1;
}

void conn(int a,int b){
    nodes[a].push_back(b);
    if(nodes[a].size()==3){
        num3.insert(a);
        for(int ne:nodes[a])
            num3n[ne]++;
    }
    
    if(nodes[a].size()==4){
        num3.erase(a);
        if(num4==-1)
            num4=a;
        else
            num4=-2;
        for(int ne:nodes[a])
            num3n[ne]--;
    }
}

void Link(int a,int b){
    conn(a,b);
    conn(b,a);
    
    if(dsu_get(a)==dsu_get(b)){
        if(num_cycles==0){
            cvis++;
            dfs(a,0,a);
            for(int i=0;i<1e6;i++)
                if(vis[i]==cvis){
                    cycle.insert(i);
                }
            num_cycles=1;
        }else if(num_cycles==1){
            if(vis[a])
                swap(a,b);
            if(vis[a]){
                if(vis[a]!=vis[b]){
                    num_cycles=2;
                    return;
                }
                
                if(cycle.count(a)&&cycle.count(b)){
                    cycle={a,b};
                }else{
                    num_cycles=2;
                }
                return;
            }
            
            unordered_set<int>s;
            int cnt=0;
            for(int ne:nodes[a]){
                cvis++;
                vis[a]=cvis;
                int r=dfs(ne,1,a);
                if(r!=-1){
                    s.insert(r);
                    cnt++;
                }
            }
            
            //cout<<"CNT: "<<cnt<<"\n";
            if(s.size()!=1||cnt!=2){
                num_cycles=2;
            }else{
                int center=*s.begin();
                if(cycle.find(center)!=cycle.end()){
                    cycle={center};
                    //cout<<"CYCLE: "<<center<<"\n";
                }else
                    num_cycles=2;
            }
        }else{
            num_cycles=2;
        }
    }else{
        dsu_merge(a,b);
    }
}

bool check(int i){
    bool in_cycle=true;
    if(num_cycles==1)
        in_cycle=cycle.find(i)!=cycle.end();
    /*cout<<"checking "<<i<<"\n";
    cout<<(num3n[i]==(int)num3.size())<<" ";
    cout<<(nodes[i].size()==3&&num3n[i]==(int)num3.size()-1)<<" ";
    cout<<in_cycle<<"\n";*/
    return (num3n[i]==(int)num3.size()||(nodes[i].size()==3&&num3n[i]==(int)num3.size()-1))&&in_cycle;
}

int CountCritical(){
    if(num_cycles>=2)
        return 0;
    if(num3.size()>4)
        return 0;
    if(num4==-2)
        return 0;
    if(num4!=-1){
        bool in_cycle=true;
        if(num_cycles==1)
            in_cycle=cycle.find(num4)!=cycle.end();
        return num3n[num4]==num3.size()&&in_cycle;
    }
    
    if(num3.empty()&&num_cycles==1)
        return cycle.size();
    
    if(num3.empty())
        return n;
    
    int res=0;
    unordered_set<int>s;
    for(int i:num3){
        for(int ne:nodes[i]){
            if(check(ne))
                s.insert(ne);
        }
        if(check(i))
            s.insert(i);
    }
    return (int)s.size();
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:163:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         return num3n[num4]==num3.size()&&in_cycle;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~
rings.cpp:172:9: warning: unused variable 'res' [-Wunused-variable]
  172 |     int res=0;
      |         ^~~

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