Submission #587272

#	Time	Username	Problem	Language	Result	Execution time	Memory
587272		GioChkhaidze	Parachute rings (IOI12_rings)	C++14	100 / 100	1837 ms	262144 KiB

rings

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 1e6 + 6;

bool cycle, us[Nn];
int n, p[Nn], sz[Nn], pr[Nn], cr[Nn];
vector < int > v[Nn];
set < int > ans;

int P(int x) {
	if (p[x] == x) return x;
	return p[x] = P(p[x]);
}

void Init(int N_) {
	n = N_;
	for (int i = 0; i < n; ++i) {
		ans.insert(i);
		p[i] = i;
	}
}

void intr(set < int > cur) {
	int crs = 0;
	for (set < int > :: iterator it = cur.begin(); it != cur.end(); ++it) {
		if (ans.find(*it) == ans.end()) continue;
		cr[++crs] = (*it);
	}
	ans.clear();
	for (int i = 1; i <= crs; ++i) {
		ans.insert(cr[i]);
	}
}

vector < int > rec;
void dfs(int x, int p, int fn) {
	pr[x] = p;
	us[x] = true;
	rec.pb(x);
	if (x == fn)  { 
		set < int > cur;
		cur.insert(x);
		x = pr[x];
		cycle = true;
		while (x != fn) {
			cur.insert(x);
			x = pr[x];
		}
		intr(cur);
		return ;
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to != p && !us[to]) dfs(to, x, fn);
		if (cycle) return ;
	}
}

void Link(int A, int B) {
	int ap = P(A), bp = P(B);	
	v[A].pb(B), v[B].pb(A);

	if (ap != bp) {
		if (sz[ap] < sz[bp]) swap(ap, bp);	
		sz[ap] += sz[bp];
		p[bp] = ap;
	}
		else {
		++sz[ap];
		if (sz[ap] <= 3) {
			cycle = false;
			dfs(A, B, B);
		}
		for (int i = 0; i < rec.size(); ++i) {
			us[rec[i]] = false;
		}
		rec.clear();
		if (sz[ap] == 2) {
			set < int > cur;
			int crs = 0;
			for (set < int > :: iterator it = ans.begin(); it != ans.end(); ++it) {
				if (v[(*it)].size() >= 3) {
					cr[++crs] = (*it);
				}
			} 	
			ans.clear();
			for (int i = 1; i <= crs; ++i) {
				ans.insert(cr[i]);
			}
		}
	}
	
	set < int > st;
	if (v[A].size() == 4) st.clear(), st.insert(A), intr(st);
	if (v[B].size() == 4) st.clear(), st.insert(B), intr(st);
	if (v[A].size() == 3) st.clear(), st.insert(A), st.insert(v[A][0]), st.insert(v[A][1]), st.insert(v[A][2]), intr(st);
	if (v[B].size() == 3) st.clear(), st.insert(B), st.insert(v[B][0]), st.insert(v[B][1]), st.insert(v[B][2]), intr(st);
}

int CountCritical() {
	return ans.size();
}

Compilation message (stderr)

rings.cpp: In function 'void dfs(int, int, int)':
rings.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < rec.size(); ++i) {
      |                   ~~^~~~~~~~~~~~

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