Submission #868671

#	Time	Username	Problem	Language	Result	Execution time	Memory
868671		HuyQuang_re_Zero	Parachute rings (IOI12_rings)	C++14	100 / 100	1047 ms	129528 KiB

rings

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 1000005
using namespace std;
struct International_Olympiad_in_Informatics
{
    struct DSU
    {
        int r[N];
        int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
        void Init()
        {
            for(int u=1;u<N;u++) r[u]=u;
        }
        bool connect(int u,int v)
        {
            u=root(u); v=root(v);
            if(u==v) return 0;
            r[u]=v;
            return 1;
        }
    } DS[4];

    vector <II> edge;
    vector <int> candidate,a[N],ok1;
    int n,i,u,v,flag,cnt3,cnt4,int4,deg[N],to_3[N],num[N],n_ring,w_ring,node[N],node3[N],r[N],now[N],step;
    bool have_cycle[N];
    void Init(int _n)
    {
        n=_n;
        for(u=1;u<=n;u++) ok1.push_back(u),r[u]=u,node[u]=1;
    }
    bool check1(int u)
    {
        if(cnt4==2) return 0;
        if(cnt4==1 && deg[u]<4) return 0;
        return (to_3[u]==cnt3);
    }
    void update(int u,int k) { to_3[u]+=k; }
    void Filter(int u,int v)
    {
        vector <int> tg;
        for(int x:candidate)
            if(!((u!=x && v!=x && DS[num[x]].connect(u,v)==0) || check1(x)==0))
                tg.push_back(x);
        candidate=tg;
        return ;
    }

    int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
    void check_root(int u,int op)
    {
        if(have_cycle[u]==1 && node3[u]==0)
            n_ring+=op,w_ring+=op*node[u];
    }
    void join(int u,int v)
    {
        u=root(u); v=root(v);
        if(u==v)
        {
            check_root(u,-1);
            have_cycle[u]=1;
            check_root(u,1);
            return ;
        }
        check_root(u,-1);
        check_root(v,-1);
        r[u]=v;
        node3[v]+=node3[u];
        node[v]+=node[u];
        have_cycle[v]|=have_cycle[u];
        check_root(v,1);
    }
    void Link(int u,int v)
    {
     //  cerr<<u<<" "<<v<<'\n';
        edge.push_back({ u,v });
        a[u].push_back(v); a[v].push_back(u);
        deg[u]++; deg[v]++;
        cnt3+=(deg[u]==3)+(deg[v]==3);
        cnt4+=(deg[u]==4)+(deg[v]==4);
        update(u,(deg[u]==3)+(deg[v]>=3));
        update(v,(deg[v]==3)+(deg[u]>=3));
        check_root(root(u),-1);
        node3[root(u)]+=(deg[u]==3);
        check_root(root(u),1);
        check_root(root(v),-1);
        node3[root(v)]+=(deg[v]==3);
        check_root(root(v),1);
        join(u,v);
        if(deg[u]==3)
        {
            for(int x:a[u])
                if(x!=v) update(x,1);
        }
        if(deg[v]==3)
        {
            for(int x:a[v])
                if(x!=u) update(x,1);
        }
        if(flag) Filter(u,v);
        else
        {
            if(cnt4==2) { step++; ok1.clear(); }
            if(cnt4==1)
            {
                step++;
                vector <int> tg;
                for(int u:ok1)
                    if(check1(u)) tg.push_back(u),now[u]=step;
                ok1=tg;
            }
            if(deg[u]==3 || deg[v]==3)
            {
                step++;
                vector <int> tg;
                if(deg[u]==3)
                {
                    for(int x:a[u])
                        if(now[x]==step-1 && check1(x)) now[x]=step,tg.push_back(x);
                    if(now[u]==step-1 && check1(u)) now[u]=step,tg.push_back(u);
                }
                if(deg[v]==3)
                {
                    for(int x:a[v])
                        if(now[x]==step-1 && check1(x)) now[x]=step,tg.push_back(x);
                    if(now[v]==step-1 && check1(v)) now[v]=step,tg.push_back(v);
                }
                ok1=tg;
            }



            if(ok1.size()<=4)
            {
                flag=1;
                for(int u:ok1)
                {
                    num[u]=candidate.size();
                    candidate.push_back(u);
                    DS[num[u]].Init();
                }
                for(II x:edge) Filter(x.fst,x.snd);
            }
        }
    }
    int Cal()
    {
        if(n_ring>1) return 0;
        if(n_ring==1)
        {
            if(cnt3>0) return 0;
            return w_ring;
        }
        return (flag==0) ? ok1.size() : candidate.size();
    }
} IOI;


void Init(int _n) { IOI.Init(_n); }
void Link(int u,int v) { IOI.Link(u+1,v+1); }
int CountCritical() { return IOI.Cal(); }
int n,u,v,type,q;
/*
int main()
{
    freopen("rings.inp","r",stdin);
    freopen("rings.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q; Init(n);
    while(q--)
    {
        cin>>u;
        if(u>-1) cin>>v,Link(u,v);
        else cout<<CountCritical()<<'\n';
    }
}

*/

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