Submission #1161124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161124		sano	Parachute rings (IOI12_rings)	C++20	37 / 100	1525 ms	213016 KiB

rings

//#include "crocodile.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<int> poc;
int pocet4 = 0;
vec<vec<int>> g;
int faza2 = 0;
vec<int> o;
vec<vec<int>> mp;
int n;

int otec(int x) {
	if (o[x] < 0) return x;
	o[x] = otec(o[x]);
	return o[x];
}

set<int> r;

void Init(int n2) {
	n = n2;
	g.resize(n);
	mp.resize(n);
	For(i, n) mp[i].push_back(i);
	o.resize(n, -1);
	poc.resize(n, 0);
	For(i, n) r.insert(i);
	return;
}

void Link(int a, int b) {
	poc[a]++; poc[b]++;
	g[a].push_back(b);
	g[b].push_back(a);
	if (poc[a] == 4) {
		pocet4++;
		r.clear();
		if(pocet4 == 1) r.insert(a);
	}
	if (poc[a] == 3) {
		faza2 = 1;
		set<int> r2;
		if (r.find(a) != r.end()) {
			r2.insert(a);
		}
		for (auto i : g[a]) {
			if (r.find(i) != r.end()) {
				r2.insert(i);
			}
		}
		r = r2; r2.clear();
	}
	if (poc[b] == 4) {
		pocet4++;
		r.clear();
		if(pocet4 == 1) r.insert(b);
	}
	if (poc[b] == 3) {
		faza2 = 1;
		set<int> r2;
		if (r.find(b) != r.end()) {
			r2.insert(b);
		}
		for (auto i : g[b]) {
			if (r.find(i) != r.end()) {
				r2.insert(i);
			}
		}
		r = r2; r2.clear();
	}
	if (faza2 != 0) return;
	if (otec(a) != otec(b)) {
		a = otec(a);
		b = otec(b);
		if (mp[a].size() < mp[b].size()) swap(a, b);
		o[otec(b)] = otec(a);
		for (auto i : mp[b]) mp[a].push_back(i);
		mp[b].clear();
	}
	else {
		a = otec(a);
		b = otec(b);
		set<int> r2;
		for (auto i : mp[a]) {
			if (r.find(i) != r.end()) {
				r2.insert(i);
			}
		}
		r = r2; r2.clear();
	}
	return;
}

bool dfs(int x, int pr, int s, vec<bool>&bol) {
	if (bol[x]) return 0;
	bol[x] = 1;
	int k = 0;
	bool je = 1;
	for (auto i : g[x]) {
		if (i == s) continue;
		k++;
		if (i == pr) continue;
		je &= dfs(i, x, s, bol);
	}
	if (k > 2) je = 0;
	return je;
}

int check(int x) {
	bool je = 1;
	vec<bool> bol(n, false);
	for (auto i : g[x]) {
		if (bol[i]) continue;
		je &= dfs(i, x, x, bol);
	}
	return je;
}

int CountCritical() {
	if (faza2 == 0) {
		return r.size();
	}
	if (faza2 == 1) {
		int vys = 0;
		for (auto i : r) {
			vys += check(i);
		}
		return vys;
	}

	return 0;
}

/*
signed main() {
	//ll t; cin >> t;
	ll t = 1;
	For(w, t){
		int n, q; cin >> n >> q;
		Init(n);
		For(i, q) {
			int x; cin >> x;
			if (x == -1) {
				cout << CountCritical() << '\n';
			}
			else {
				int y; cin >> y;
				Link(x, y);
			}
		}
	}
	return 0;
}*/

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