Submission #1017958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017958		pcc	Parachute rings (IOI12_rings)	C++17	100 / 100	999 ms	161400 KiB

rings

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e6+10;

int phase;
int N;
bool initflag = false;

struct DSU{
	int cnt[mxn][4];//deg = 0,deg = 1,deg = 2,deg>2
	int dsu[mxn],sz[mxn],deg[mxn];
	int good,cycle;
	int WA = false;
	void init(int n){
		good = true;
		cycle = -1;
		for(int i = 0;i<n;i++){
			dsu[i] = i,sz[i] = 1;
			memset(cnt[i],0,sizeof(cnt[i]));
			cnt[i][0] = 1;
		}
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void check(int a){
		a = root(a);
		if(cnt[a][3])good = false,cycle = -1;
		else if(!cnt[a][1]&&cycle != -1)WA = true;
		else if(!cnt[a][1])cycle = a;
		return;
	}
	void del(int k){
		int r = root(k);
		cnt[r][min(deg[k],3)]--;
		return;
	}
	void add(int k){
		int r = root(k);
		cnt[r][min(deg[k],3)]++;
		return;
	}
	void add_edge(int a,int b){
		del(a);deg[a]++;add(a);
		del(b);deg[b]++;add(b);
		a = root(a),b = root(b);
		if(a != b){
			if(sz[a]<sz[b])swap(a,b);
			dsu[b] = a;
			sz[a] += sz[b];
			for(int i = 0;i<4;i++)cnt[a][i] += cnt[b][i];
		}
		check(a);
		return;
	}
};

vector<pii> edges;


namespace PHASE1{
	DSU dsu;
	void INIT(){
		//cerr<<"PHASE 1 init!"<<endl;
		dsu.init(N);
		//cerr<<"PHASE 1 INIT DONE!"<<endl;
	}
	void ADD(int a,int b){
		//cerr<<"PHASE 1 add: "<<a<<','<<b<<endl;
		dsu.add_edge(a,b);
		if(!dsu.good){
			phase = 2;
			initflag = true;
		}
		//cerr<<"PHASE 1 add done!"<<endl;
		return;
	}
	int CALC(){
		//cerr<<"PHASE 1 CALC"<<endl;
		if(dsu.WA)return 0;
		if(dsu.cycle != -1)return dsu.sz[dsu.root(dsu.cycle)];
		else return N;
	}
}

namespace PHASE2{
	struct GRAPH{
		DSU dsu;
		int ban;
		GRAPH(int k = -1){
			ban = k;
			dsu.init(N);
		}
		void add_edge(int a,int b){
			if(a == ban||b == ban)return;
			dsu.add_edge(a,b);
			//cerr<<"ADD_EDGE: "<<ban<<','<<a<<' '<<b<<':'<<dsu.cycle<<endl;
			return;
		}
		bool isgood(){
			return dsu.good&&dsu.cycle == -1;
		}
	};

	GRAPH v[5];
	int ptr = 0;
	void INIT(){
		//cerr<<"PHASE 2 INIT!"<<endl;
		//cerr<<"PHASE 2 INIT!"<<endl;
		int fat = -1;
		ptr = 0;
		for(int i = 0;i<N;i++)if(PHASE1::dsu.deg[i] >= 3)fat = i;
		assert(fat != -1);
		v[ptr++].ban = fat;
		for(auto &i:edges){
			if(i.fs == fat)v[ptr++].ban = i.sc;
			if(i.sc == fat)v[ptr++].ban = i.fs;
		}
		for(int i = 0;i<ptr;i++)v[i].dsu.init(N);
		//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
		for(auto &i:edges){
			for(int j = 0;j<ptr;j++)v[j].add_edge(i.fs,i.sc);
		}
		//cerr<<"SPECIALS: ";for(int i = 0;i<ptr;i++)cerr<<v[i].ban<<' '<<v[i].dsu.cycle<<',';cerr<<endl;
		//cerr<<"PHASE 2 INIT DONE!"<<endl;
	}
	void ADD(int a,int b){
		//cerr<<"PHASE 2 ADD: "<<a<<','<<b<<endl;
		for(int i = 0;i<ptr;i++)v[i].add_edge(a,b);
		//cerr<<"PHASE 2 ADD DONE!"<<endl;
		return;
	}
	int CALC(){
		//cerr<<"PHASE 2 CALC"<<endl;
		if(PHASE1::dsu.WA)return 0;
		int ans = 0;
		for(int i = 0;i<ptr;i++)ans += v[i].isgood();
		return ans;
	}
}

void Init(int N_) {
	edges.clear();
	phase = 1;
	N = N_;
	PHASE1::INIT();
}

void Link(int A, int B) {
	edges.push_back(pii(A,B));
	if(phase == 1)PHASE1::ADD(A,B);
	else PHASE2::ADD(A,B);
	if(initflag){
		//cerr<<"PHASE 2 INIT!"<<endl;
		PHASE2::INIT();
		initflag = false;
	}
	return;
}

int CountCritical() {
	if(phase == 1)return PHASE1::CALC();
	else return PHASE2::CALC();
}

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