oj.uz

Submission #577049

# Submission time Handle Problem Language Result Execution time Memory
577049 2022-06-13T23:24:25 Z PedroBigMan Parachute rings (IOI12_rings) C++14
0 / 100
 1720 ms 181148 KB 
/*
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1184 KB Output is correct
3 Correct 3 ms 1320 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 47876 KB Output is correct
2 Correct 1507 ms 149720 KB Output is correct
3 Correct 1720 ms 181148 KB Output is correct
4 Incorrect 995 ms 91880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1184 KB Output is correct
3 Correct 3 ms 1320 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1184 KB Output is correct
3 Correct 3 ms 1320 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1184 KB Output is correct
3 Correct 3 ms 1320 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -