Submission #382378

#	Time	Username	Problem	Language	Result	Execution time	Memory
382378		Keshi	Parachute rings (IOI12_rings)	C++17	100 / 100	1213 ms	87148 KiB

rings

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, m, t, cntdor, szdor, cnt3, cnt4;
pll e[maxn];

struct gr{
	ll x, a[maxn];
	bool ok;
	gr(ll y = 0){
		x = y;
		ok = 1;
		return;
	}
	void add(ll v, ll u){
		//cout << "! " << x << "\n";
		//cout << " add " << v << " " << u << "\n";
		if(v == x || u == x) return;
		ll av = a[v], au = a[u];
		if(av == u || av == -1 || au == -1){
			//cout << " --- fail ---- \n";
			ok = 0;
			return;
		}
		a[v] = -1;
		a[u] = -1;
		a[av] = au;
		a[au] = av;
		//for(ll i = 0; i < n; i++){
		//	cout << a[i] << " ";
		//}
		//cout << "\n----------\n";
		return;
	}
};

vector<ll> g[maxn];
bool ride, done[maxn];
ll dsu[maxn], sz[maxn], dr[maxn];
gr d[20];

ll par(ll v){
	if(dsu[v] != v) dsu[v] = par(dsu[v]);
	return dsu[v];
}

ll Union(ll v, ll u){
	v = par(v);
	u = par(u);
	if(v == u){
		if(dr[v]) return 0;
		dr[v] = 1;
		return sz[v];
	}
	if(sz[v] < sz[u]) swap(v, u);
	dsu[u] = v;
	sz[v] += sz[u];
	return 0;
}

void Do(ll v){
	if(done[v]) return;
	//cout << "# " << t << " -> " << v << "\n";
	done[v] = 1;
	cnt3++;
	d[t].x = v;
	d[t].ok = 1;
	for(ll i = 0; i < n; i++){
		d[t].a[i] = i;
	}
	for(ll i = 0; i < m; i++){
		d[t].add(e[i].F, e[i].S);
	}
	t++;
	return;
}
void Init(int N){
	n = N;
	for(ll i = 0; i < n; i++){
		dsu[i] = i;
		sz[i] = 1;
	}
}
void Link(int A, int B){
	g[A].pb(B);
	g[B].pb(A);
	if(Sz(g[A]) == 3 && cnt3 < 4){
		Do(A);
		for(ll u : g[A]){
			Do(u);
		}
	}
	if(Sz(g[B]) == 3 && cnt3 < 4){
		Do(B);
		for(ll u : g[B]){
			Do(u);
		}
	}
	if(Sz(g[A]) == 4 && cnt4 < 1){
		if(!done[A]){
			cnt3--;
			cnt4++;
		}
		Do(A);
	}
	if(Sz(g[B]) == 4 && cnt4 < 1){
		if(!done[B]){
			cnt3--;
			cnt4++;
		}
		Do(B);
	}
	e[m++] = Mp(A, B);
	for(ll i = 0; i < t; i++){
		d[i].add(A, B);
	}
	ll x = Union(A, B);
	if(x){
		if(cntdor) ride = 1;
		cntdor++;
		szdor += x;
	}
	return;
}
int CountCritical(){
	if(ride) return 0;
	if(t == 0){
		if(cntdor == 0) return n;
		return szdor;
	}
	ll ans = 0;
	for(ll i = 0; i < t; i++){
		if(d[i].ok) ans++;
	}
	return ans;
}


/*int main(){
    //fast_io;
    
    ll n, m;
    cin >> n >> m;
    Init(n);
    for(ll i = 0; i < m; i++){
    	ll x, y;
    	cin >> x;
    	if(x == -1){
    		cout << CountCritical() << "\n";
		}
		else{
			cin >> y;
			Link(x, y);
		}
	}
 
    return 0;
}*/

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