Submission #907525

#	Time	Username	Problem	Language	Result	Execution time	Memory
907525		JakobZorz	Parachute rings (IOI12_rings)	C++17	37 / 100	1361 ms	139536 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_has_cycle[(int)1e6];
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_has_cycle[a]=max(dsu_has_cycle[a],dsu_has_cycle[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);
            //cout<<"cycle: ";
            for(int i=0;i<1e6;i++)
                if(vis[i]==cvis){
                    cycle.insert(i);
                    //cout<<i<<" ";
                }
            //cout<<"\n";
            num_cycles=1;
        }else if(num_cycles==1){
            if(dsu_has_cycle[dsu_get(a)]==0)
                num_cycles=2;
            else{
                unordered_set<int>s;
                for(int ne:nodes[a]){
                    cvis++;
                    int r=dfs(a,0,a);
                    if(r!=-1)
                        s.insert(r);
                }
                
                if(s.size()!=1){
                    num_cycles=2;
                }else{
                    int center=*s.begin();
                    if(cycle.count(center))
                        cycle={center};
                    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.count(i);
    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.count(num4);
        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 'void Link(int, int)':
rings.cpp:103:25: warning: unused variable 'ne' [-Wunused-variable]
  103 |                 for(int ne:nodes[a]){
      |                         ^~
rings.cpp: In function 'int CountCritical()':
rings.cpp:146:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         return num3n[num4]==num3.size()&&in_cycle;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~
rings.cpp:155:9: warning: unused variable 'res' [-Wunused-variable]
  155 |     int res=0;
      |         ^~~

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