oj.uz

Submission #1104997

# Submission time Handle Problem Language Result Execution time Memory
1104997 2024-10-25T06:10:18 Z Nonoze Parachute rings (IOI12_rings) C++17
0 / 100
 513 ms 150536 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);}
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define QYES quit("YES")
#define QNO quit("NO")

// #define int long long
#define double long double
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;

int n, cnt;
vector<int> par, sz;
vector<vector<int>> contains;
vector<set<int>> adj;
set<pair<int, int>> critical;

int find(int x) {
	if (x==par[x]) return x;
	return par[x] = find(par[x]);
}

bool same(int a, int b) {
	return find(a)==find(b);
}

void merge(int a, int b) {
	a = find(a), b = find(b);
	if (a==b) return;
	if (sz[a]<sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
	for (int i=1; i<4; i++) {
		contains[a][i] += contains[b][i];
	}
}

bool works(int a) {
	a=find(a);
	if (sz[a]<=2) return 1;
	if (contains[a][1]==2 && contains[a][3]==0) return 1;
	return 0;
}

void Init(int N_) {
	n = N_;
	cnt=n;
	par.resize(n), sz.resize(n, 1), contains.resize(n, vector<int>(4, 0));
	iota(all(par), 0);
	adj.resize(n);
	for (int i=0; i<n; i++) critical.insert({i, 1});
}

void Link(int a, int b) {
	if (critical.empty()) return;
	if (a>b) swap(a, b);
	if (same(a, b) || sz(adj[a])>=2 || sz(adj[b])>=2) {
		if (sz(adj[a])>=3 || sz(adj[b])>=3) {
			int cnta=critical.count({a, 1})||critical.count({a, 0}), cntb=critical.count({b, 1})||critical.count({b, 0});
			critical.clear();
			if (sz(adj[a])<3 && cnta) critical.insert({a, 1});
			else if (sz(adj[b])<3 && cntb) critical.insert({b, 1});
			return;
		}
		if (sz(critical)==n) {
			critical.clear();
			for (int i=0; i<n; i++) {
				if (i==a || i==b || (find(i)==find(a) && sz(adj[a])<2 && sz(adj[b])<2)) {
					critical.insert({i, 1});
				} else if (adj[a].count(i) || adj[b].count(i)) {
					critical.insert({i, 0});
				}
			}
		} else {
			set<pair<int, int>> neww;
			for (auto u: critical) {
				if (u.fi==a || u.fi==b) {
					neww.insert({u.fi, 1});
				} else if ((adj[a].count(u.fi) || adj[b].count(u.fi))) {
					neww.insert({u.fi, 0});
				}
			}
			critical=neww;
		}
		merge(a, b);
		contains[find(a)][sz(adj[a])]--, contains[find(b)][sz(adj[b])]--;
		adj[a].insert(b), adj[b].insert(a);
		contains[find(a)][sz(adj[a])]++, contains[find(a)][sz(adj[b])]++;
		return;
	}
	merge(a, b);
	contains[find(a)][sz(adj[a])]--;
	contains[find(b)][sz(adj[b])]--;
	adj[a].insert(b), adj[b].insert(a);
	contains[find(a)][sz(adj[a])]++;
	contains[find(b)][sz(adj[b])]++;
}

int CountCritical() {
	return sz(critical);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 130376 KB Output is correct
2 Incorrect 500 ms 150536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -