Submission #1012119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012119		amirhoseinfar1385	Parachute rings (IOI12_rings)	C++17	100 / 100	1372 ms	262144 KiB

rings

#include<bits/stdc++.h>
//#include "rings.h"
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
const int maxn=1000000+10;
vector<int>cand;
int n,tof=0;
struct gr{
	pair<int,int>mx;
	int par[maxn],sz[maxn],dordare,m,c,moalefedordar;
	vector<int>adjs[maxn];
	void clear(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
			adjs[i].clear();
		}
		mx=make_pair(0,-1);
		m=0;
		dordare=moalefedordar=c=m=0;
	}
	gr(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
		mx=make_pair(0,-1);
		m=0;
		dordare=moalefedordar=c=m=0;
	}
	void con(int u,int v){
		m++;
		if(adjs[u].size()<=3){
			adjs[u].push_back(v);
		}
		if(adjs[v].size()<=3){
			adjs[v].push_back(u);
		}
		mx=max(mx,make_pair((int)adjs[u].size(),u));
		mx=max(mx,make_pair((int)adjs[v].size(),v));
		if(par[u]==v){
			dordare++;
			moalefedordar=sz[u];
		}else{
			c--;
			int pu=par[u],pv=par[v],x=sz[u]+sz[v];
			sz[pu]=x;
			sz[pv]=x;
			par[pu]=pv;
			par[pv]=pu;
		}
	}
}gr[4];

void Init(int N){
	//int n=N;
	n=N;
	for(int i=0;i<4;i++){
		gr[i].c=n;
	}
}
vector<pair<int,int>>getalle(){
	vector<pair<int,int>>ret;
	for(int i=0;i<n;i++){
		for(auto x:gr[0].adjs[i]){
			if(x>i){
				ret.push_back(make_pair(i,x));
			}
		}
	}
	return ret;
}

void Link(int A, int B){
	int u=A;
	int v=B;
	if(tof==0){
		gr[0].con(u,v);
	}
	if((int)cand.size()>0){
		for(int i=0;i<4;i++){
			if(gr[i].dordare==1||gr[i].mx.first>=3||u==cand[i]||v==cand[i]){
				continue;
			}
			gr[i].con(u,v);
		}
	}
	if(tof==0&&(gr[0].mx).first>=3){
		tof=1;
		int z=(gr[0].mx).second;
		for(auto x:gr[0].adjs[z]){
			cand.push_back(x);
		}
		cand.push_back(z);
		vector<pair<int,int>>v=getalle();
		gr[0].clear();
		for(int i=0;i<(int)cand.size();i++){
			for(auto x:v){
				if(gr[i].dordare==1||gr[i].mx.first>=3||x.first==cand[i]||x.second==cand[i]){
					continue;
				}
				gr[i].con(x.first,x.second);
			}
		}
	}
}

int CountCritical(){
	if(tof){
		int res=0;
		for(int i=0;i<4;i++){
			if(gr[i].dordare==0&&(gr[i].mx).first<3){
				res++;
			}
		}
		return res;
	}
	if(gr[0].dordare==0){
		return n;
	}
	if(gr[0].dordare>=2){
		return 0;
	}
	return gr[0].moalefedordar;
}

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