Submission #286702

#	Time	Username	Problem	Language	Result	Execution time	Memory
286702		amiratou	Parachute rings (IOI12_rings)	C++14	37 / 100	2838 ms	177920 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;

int N,degree[MX],id[MX],idx,t=1;
vector<int> vec[MX];
multiset<int,greater<int> > comp[MX];
int vis[MX];

void Init(int N_) {
	N = N_;
}

void Link(int A, int B) {
	vec[A].pb(B),vec[B].pb(A);
	degree[A]++,degree[B]++;
}
void dfs(int node,int k=0){
	vis[node]=t;
	if(!k){
		id[node]=idx;
		comp[idx].insert(degree[node]);
	}
	for(auto it:vec[node])
		if(vis[it]!=t)dfs(it,k);
}
int gimme(int node){
	vis[node]=t;
	int h=0;
	for(auto it:vec[node])
		if(vis[it]!=t)dfs(it,1),h++;
	return h;
}

int CountCritical() {
	idx=0;
	for (int i = 0; i < N; ++i)
		vis[i]=0,comp[i].clear();
	for (int i = 0; i < N; ++i)
		if(vis[i]!=t)dfs(i),idx++;
	set<int> good;
	for (int i = 0; i < idx; ++i)
	{
		if(sz(comp[i])==1)good.insert(i);
		else if((*comp[i].begin())<=2 && comp[i].find(1)!=comp[i].end()){
			comp[i].erase(comp[i].find(1));
			bool f=0;
			if(comp[i].find(1)!=comp[i].end())f=1;
			comp[i].insert(1);
			if(f)good.insert(i);
		}
	}
	//cerr<<idx<<","<<sz(good)<<"\n";
	int ans=0;
	for (int i = 0; i < N; ++i)
	{
		bool g=0;
		if(good.find(id[i])!=good.end())good.erase(id[i]),g=1;
		if(sz(good)==(idx-1)){
			bool bad=1;
			int one=0,zero=0,nb=0;
			comp[id[i]].erase(comp[id[i]].find(degree[i]));
			for(auto it:vec[i]){
				comp[id[i]].erase(comp[id[i]].find(degree[it]));
				degree[it]--;
				if(!degree[it])zero++;
				//else if(degree[it]==2)nb--;
				comp[id[i]].insert(degree[it]);
			}
			if(sz(comp[id[i]])<=2)bad=0;
			else if((*comp[id[i]].begin())<=2){
				t++;
				auto it=comp[id[i]].lower_bound(1);
				while(it!=comp[id[i]].end()){
					if(*it)one++;
					else break;
					it++;
				}
				/*cerr<<"deg : "<<degree[i]<<"\n";
				cerr<<i<<" "<<one<<" "<<zero<<"\n";*/
				if(N<=5000){
					nb=gimme(i);
					if(!(one&1) && ((one/2 + zero)==nb))bad=0;
				}
				else if(!(one&1))bad=0;
			}
			if(!bad)ans++;
			for(auto it:vec[i]){
				comp[id[i]].erase(comp[id[i]].find(degree[it]));
				degree[it]++;
				comp[id[i]].insert(degree[it]);
			}
			comp[id[i]].insert(degree[i]);
		}
		if(g)good.insert(id[i]);
	}
	//cerr<<"\n---------\n";
	return ans;

}

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