Submission #68729

#	Time	Username	Problem	Language	Result	Execution time	Memory
68729		Abelyan	Parachute rings (IOI12_rings)	C++17	0 / 100	4034 ms	110244 KiB

rings

//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;


const int N=1000006;
int p[12][N],sz[12][N],deg[12][N],degcn[12][N],n,comp[12],qanak,an;
vector<int> g[N],d3;
bool no=false,col[N],cnch[N],bl;

int get_par(int v,int k){
    if (p[k][v]==v)return v;
    return p[k][v]=get_par(p[k][v],k);
}

void unite (int a,int b,int k=0){
    a=get_par(a,k);
    b=get_par(b,k);
    if (a!=b){
        comp[k]--;
        if (sz[k][b]>sz[k][a])swap(a,b);
        p[k][b]=a;
        sz[k][a]+=sz[k][b];
    }
    else if (k==0){
        //cout<<"hi"<<endl;
        if (bl)an=0;
        else {
            an=sz[0][a];
        }
    }
}

void Init(int N_) {
    n=N_;
    degcn[0][0]=n;
    comp[0]=n;
    for (int i=0;i<n;i++){
        p[0][i]=i;
        sz[0][i]=1;
    }
}


void make_dsu(int b,int k){
    comp[k]=n-1;
    for (int i=0;i<n;i++){
        p[k][i]=i;
        sz[k][i]=i;
    }
    for (int i=0;i<n;i++){
        if (i==b)continue;
        for (int j=0;j<g[i].size();j++){
            if (g[i][j]==b)continue;
            unite(i,g[i][j],k);
            deg[k][i]++;
            deg[k][g[i][j]]++;
            //if (b==1)
            //cout<<"hi "<<deg[k][i]<<" "<<deg[k][g[i][j]]<<" "<<i<<" "<<g[i][j]<<endl;
        }
    }
    for (int i=0;i<n;i++){
        deg[k][i]/=2;
        if (i==b)continue;
        degcn[k][deg[k][i]]++;
        //cout<<k<<" "<<degcn[k][deg[k][i]]<<" ";
    }
    //cout<<endl;
}

void Link(int a, int b) {
    //if (no) return;
    g[a].push_back(b);
    g[b].push_back(a);
    deg[0][a]++;
    deg[0][b]++;
    degcn[0][deg[0][a]-1]--;
    degcn[0][deg[0][b]-1]--;
    degcn[0][deg[0][a]]++;
    degcn[0][deg[0][b]]++;
    unite(a,b);
    vector<int> v;
    if (deg[0][a]==3 && qanak<1){
    //cout<<a<<"A"<<endl;
        qanak++;
        col[a]=true;
        d3.push_back(a);
        make_dsu(a,d3.size());
        v.push_back(d3.size());
        cnch[d3.size()]=true;
        for (int i=0;i<g[a].size();i++){
            if (col[g[a][i]])continue;
            //cout<<g[a][i]<<" ";
            col[g[a][i]]=true;
            d3.push_back(g[a][i]);
            v.push_back(d3.size());
            cnch[d3.size()]=true;
            make_dsu(g[a][i],d3.size());
        }
            //cout<<endl;
    }
    if (deg[0][b]==3 && qanak<1){
    //cout<<a<<"A"<<endl;
        qanak++;
        col[b]=true;
        d3.push_back(b);
        make_dsu(b,d3.size());
        v.push_back(d3.size());
        cnch[d3.size()]=true;
        for (int i=0;i<g[b].size();i++){
            if (col[g[b][i]])continue;
            //cout<<g[b][i]<<" ";
            col[g[b][i]]=true;
            d3.push_back(g[b][i]);
            //cout<<d3.size()<<" ";
            v.push_back(d3.size());
            cnch[d3.size()]=true;
            make_dsu(g[b][i],d3.size());
        }
        //cout<<endl;

    }

    for (int i=0;i<d3.size();i++){
        i++;
        if (a==d3[i-1] || b==d3[i-1] || cnch[i])
        {
            i--;
            continue;
        }
        deg[i][a]++;
        deg[i][b]++;
        degcn[i][deg[i][a]-1]--;
        degcn[i][deg[i][b]-1]--;
        degcn[i][deg[i][a]]++;
        degcn[i][deg[i][b]]++;
        unite(a,b,i);
        i--;
    }
    for (int i=0;i<v.size();i++)cnch[v[i]]=false;
    //cout<<d3.size()<<endl;
}

int CountCritical() {
    //if (no)return 0;
    if (d3.size()==0){
        if (an) return an;
        if (degcn[0][0]+degcn[0][1]/2==comp[0]) return n;
        return 0;
    }
    int ans=0;
    //cout<<d3.size()<<endl;
    for (int i=0;i<d3.size();i++){
        //cout<<d3[i]<<" "<<degcn[i+1][2]<<" "<<degcn[i+1][1]<<" "<<degcn[i+1][0]<<endl;
        if (degcn[i+1][2]+degcn[i+1][1]+degcn[i+1][0]!=n-1)continue;
        if (degcn[i+1][0]+degcn[i+1][1]/2==comp[i+1]){

            ans++;
        }
    }
    //cout<<endl;
    return ans;
}

Compilation message (stderr)

rings.cpp: In function 'void make_dsu(int, int)':
rings.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<g[i].size();j++){
                      ~^~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<g[a].size();i++){
                      ~^~~~~~~~~~~~
rings.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<g[b].size();i++){
                      ~^~~~~~~~~~~~
rings.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<d3.size();i++){
                  ~^~~~~~~~~~
rings.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v.size();i++)cnch[v[i]]=false;
                  ~^~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:153:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<d3.size();i++){
                  ~^~~~~~~~~~

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