Submission #868662

#	Time	Username	Problem	Language	Result	Execution time	Memory
868662		HuyQuang_re_Zero	Parachute rings (IOI12_rings)	C++14	0 / 100	4051 ms	155764 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];
    set <II> ok1;
    int n,i,u,v,flag,cnt3,cnt4,int4,deg[N],to_3[N],num[N];
    void Init(int _n)
    {
        n=_n;
        for(u=1;u<=n;u++) ok1.insert({ 0,u });
    }
    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;
        if(ok1.find({ to_3[u]-k,u })==ok1.end()) return ;
        ok1.erase({ to_3[u]-k,u });
        ok1.insert({ to_3[u],u });
    }
    void Filter(int u,int v)
    {
        for(int x:candidate)
            if((u!=x && v!=x && DS[num[x]].connect(u,v)==0) || check1(x)==0)
                num[x]=-1;
        vector <int> tg;
        for(int x:candidate)
            if(num[x]>-1) tg.push_back(x);
        candidate=tg;
        return ;
    }
    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));
        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) ok1.clear();
            if(cnt4==1)
            {
                set <II> tg;
                for(II x:ok1)
                    if(check1(x.snd)) tg.insert(x);
                ok1=tg;
            }
            while(ok1.size()>0)
            {
                int u=ok1.begin()->snd;
                if(check1(u)) break;
                ok1.erase(ok1.begin());
            }
            if(ok1.size()<=4)
            {
                flag=1;
                for(II x:ok1)
                {
                    int u=x.snd;
                    num[u]=candidate.size();
                    candidate.push_back(u);
                    DS[num[u]].Init();
                }
             //   cerr<<candidate.size()<<'\n';
                for(II x:edge) Filter(x.fst,x.snd);
            }
        }
    }
    int Cal()
    {
        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;
char type;
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; Init(n);
    while(cin>>type)
        if(type=='L') cin>>u>>v,Link(u,v);
        else cout<<CountCritical()<<'\n';
}
*/

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