Submission #880183

#	Time	Username	Problem	Language	Result	Execution time	Memory
880183		abcvuitunggio	Parachute rings (IOI12_rings)	C++17	37 / 100	1309 ms	110036 KiB

rings

#include <vector>
using namespace std;
int n,focused=-1,ch[5],cnt,mx,deg[1000001],deg2[1000001],p[1000001][5],cycle,cyclesize,sz[1000001][5];
vector <int> candidates,ke[1000001];
vector <pair <int, int>> edge;
void reset(int j){
    for (int i=0;i<n;i++){
        p[i][j]=i;
        sz[i][j]=1;
    }
    ch[j]=1;
}
int f(int i, int j){
    return (p[i][j]==i?i:p[i][j]=f(p[i][j],j));
}
bool unite(int u, int v, int idx){
    u=f(u,idx);
    v=f(v,idx);
    if (u==v)
        return 0;
    if (sz[u][idx]<sz[v][idx])
        swap(u,v);
    sz[u][idx]+=sz[v][idx];
    p[v][idx]=u;
    return 1;
}
void focus(int node, int j=0){
    reset(j);
    if (focused!=-1)
        for (int i=0;i<n;i++)
            deg[i]=0;
    for (auto [u,v]:edge)
        if (u!=node&&v!=node){
            ch[j]&=unite(u,v,j);
            if (focused!=-1){
                deg[u]++;
                deg[v]++;
                if (max(u,v)>2)
                    ch[j]=0;
            }
        }
}
void Init(int N){
    n=N;
    for (int i=0;i<5;i++)
        reset(i);
}
void Link(int a, int b){
    edge.push_back({a,b});
    if (focused!=-1){
        if (a!=focused&&b!=focused){
            ch[0]&=unite(a,b,0);
            deg[a]++;
            deg[b]++;
            if (max(deg[a],deg[b])>2)
                ch[0]=0;
        }
        return;
    }
    deg[a]++;
    deg[b]++;
    ke[a].push_back(b);
    ke[b].push_back(a);
    if (deg[a]==4){
        focus(a);
        focused=a;
        return;
    }
    if (deg[b]==4){
        focus(b);
        focused=b;
        return;
    }
    int cnt2=cnt;
    if (deg[a]==3){
        cnt2++;
        for (int v:ke[a])
            if (deg[v]>2&&v!=b){
                deg2[a]++;
                deg2[v]++;
            }
    }
    if (deg[b]==3){
        cnt2++;
        for (int v:ke[b])
            if (deg[v]>2){
                deg2[b]++;
                deg2[v]++;
            }
    }
    if (cnt2>4){
        cnt=cnt2;
        return;
    }
    if (!cnt2){
        if (deg[a]==2&&deg[b]==2&&f(a,0)==f(b,0)){
            cycle++;
            cyclesize=sz[f(a,0)][0];
        }
        unite(a,b,0);
    }
    else if (cnt2==1){
        if (!cnt){
            if (deg[a]<deg[b])
                swap(a,b);
            candidates.push_back(a);
            for (int v:ke[a])
                candidates.push_back(v);
            for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
        }
        else{
            for (int i=0;i<candidates.size();i++)
                if (a!=candidates[i]&&b!=candidates[i])
                    ch[i]&=unite(a,b,i);
        }
    }
    else if (cnt2==2){
        if (cnt<2){
            candidates.clear();
            int u=-1,v=-1;
            for (int i=0;i<n;i++)
                if (deg[i]>2)
                    (u==-1?u=i:v=i);
            for (int i=0;i<n;i++){
                int cnt3=(i==u||i==v);
                for (int j:ke[i])
                    cnt3+=(j==u||j==v);
                if (cnt3==2)
                    candidates.push_back(i);
            }
            for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
        }
        else{
            for (int i=0;i<candidates.size();i++)
                if (a!=candidates[i]&&b!=candidates[i])
                    ch[i]&=unite(a,b,i);
        }
    }
    else if (cnt<cnt2){
        candidates.clear();
        for (int i=0;i<n;i++)
            if (deg[i]>2&&deg2[i]==cnt2-1)
                candidates.push_back(i);
        for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
    }
    else{
        for (int i=0;i<candidates.size();i++)
            if (a!=candidates[i]&&b!=candidates[i])
                ch[i]&=unite(a,b,i);
    }
    cnt=cnt2;
}
int CountCritical(){
    if (focused!=-1)
        return ch[0];
    if (cnt>4)
        return 0;
    if (cnt){
        int res=0;
        for (int i=0;i<candidates.size();i++)
            res+=ch[i];
        return res;
    }
    return (cycle>1?0:(cycle==1?cyclesize:n));
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~

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