Submission #577049

#	Time	Username	Problem	Language	Result	Execution time	Memory
577049		PedroBigMan	Parachute rings (IOI12_rings)	C++14	0 / 100	1720 ms	181148 KiB

rings

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class DSU //with range compression and union by subtree size
{
    public:
    ll N; ll CC;
    vector<ll> p,siz;
	ll d0, d1, d2, d3; vector<ll> deg;
    
	DSU() {N=0;}
    DSU(ll n)
    {
        N=n; REP(i,0,N) {p.pb(i); siz.pb(1);}
		d0=N; d1=0; d2=0; d3=0;VV(deg,N,0);
		CC=N;
    }
    
    ll find(ll x)
    {
        if(p[x]==x) {return x;}
        ll ans=find(p[x]);
        p[x]=ans; 
        return ans;
    }
    
    void unionn(ll a, ll b)
    {
		deg[a]++; deg[b]++;
		if(deg[a]==1) {d1++; d0--;} else if(deg[a]==2) {d2++; d1--;} else if(deg[a]==3) {d3++; d2--;}
		if(deg[b]==1) {d1++; d0--;} else if(deg[b]==2) {d2++; d1--;} else if(deg[b]==3) {d3++; d2--;}
        a=find(a); b=find(b);
		if(a==b) {return;}
		CC--;
        if(siz[a]>siz[b]) {swap(a,b);}
        p[a]=b; siz[b]+=siz[a];
    }
	
	ll EquivalenceClass(ll A) //O(N)
	{
		vector<ll> rep; VV(rep,N,0);
		REP(i,0,N) {rep[find(i)]++;}
		return rep[find(A)];
	}
};

ll N;
vector<vector<ll> > adj;
vector<ll> a; vector<DSU> D;
bool yet3;
DSU T; ll ed; ll C;

void Init(int N_) 
{
	N = N_; yet3=false; T = *(new DSU(N)); ed=0; C=-1; VV(adj,N,{});
}

DSU* Create_DSU(ll node)
{
	DSU *D = (new DSU(N));
	REP(i,0,N)
	{
		if(i==node) {continue;}
		REP(j,0,adj[i].size())
		{
			if(adj[i][j]==node || i>adj[i][j]) {continue;}
			(*D).unionn(i,adj[i][j]);
		}
	}
	return (D);
	
}

void Add_Node(ll node)
{
	yet3=true;
	ll nei;
	REP(i,-1,adj[node].size())
	{
		if(i==-1) {nei = node;} else {nei = adj[node][i];}
		a.pb(nei); D.pb(*Create_DSU(nei));
	}
}



void Link(int A, int B) 
{
	ed++;
	adj[A].pb(B); adj[B].pb(A);
	T.unionn(A,B);
	if(C==-1 && adj[A].size()==1 && adj[B].size()==1 && T.find(A)==T.find(B))
	{
		C=T.EquivalenceClass(A);
	}
	if(!yet3 && adj[A].size()==3) {Add_Node(A);return;} 
	if(!yet3 && adj[B].size()==3) {Add_Node(B);return;} 
	REP(i,0,a.size())
	{
		if(a[i]==A || a[i]==B) {continue;}
		D[i].unionn(A,B);
	}
}

int CountCritical() 
{
	if(yet3)
	{
		ll ans=0; 
		REP(i,0,a.size())
		{
			//cout<<a[i]<<" "<<D[i].d0<<" "<<D[i].d1<<" "<<D[i].d2<<" "<<D[i].d3<<endl;
			if(D[i].d3==0 && 2*(D[i].CC-D[i].d0)==D[i].d1) {ans++;}
		}
		return ans;
	}
	else
	{
		ll cyc = ed-(N-T.CC);
		if(cyc>=2) {return 0;} 
		else if(cyc==0) {return N;}
		else {return C;}
	}
}

Compilation message (stderr)

rings.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
rings.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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