oj.uz

Submission #382407

# Submission time Handle Problem Language Result Execution time Memory
382407 2021-03-27T09:24:46 Z aarr Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 90408 KB 
#include <bits/stdc++.h>
using namespace std;

int n, ans;
const int N = 1000 * 1000 + 5;

set <pair <int, int> > s;
vector <int> adj[N];
int deg[N];
bool g2 = false;
bool b[N];
vector <int> vec;
bool mark[N];

void Init(int N_) {
	n = N_;
	
  

}

inline int f(int v) {
	int res = 0;
	fill(mark, mark + n + 1, false);
	mark[v] = true;
	for (auto u : adj[v]) {
		deg[u]--;
	}
	for (int i = 0; i < n; i++) {
		if (i == v) {
			continue;
		}
		if (deg[i] > 2) {
			for (auto u : adj[v]) {
				deg[u]++;
			}
			return -1;
		}	
		if (deg[i] < 2) {
			int u = i;
			do {
				bool d = false;
			
				mark[u] = true;
				for (auto w : adj[u]) {
					if (!mark[w]) {
						u = w;
						d = true;
						break;
					}
				}
				if (!d) {
					break;
				}
				
			} while(u != i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			res++;
		}
	}
	for (auto u : adj[v]) {
		deg[u]++;
	}
	return res;
}

inline void check(int v) {
	if (b[v]) {
		return;
	}
	if (f(v) == 0) {
	//	cout << "72 " << v << endl;
		b[v] = true;
		ans++;
		vec.push_back(v);
	}
}

void Link(int A, int B) {
	s.erase({-deg[A], A});
	s.erase({-deg[B], B});
	deg[A]++;
	deg[B]++;
	if (deg[A] > 2 || deg[B] > 2) {
		g2 = true;
	}
	adj[A].push_back(B);
	adj[B].push_back(A);
	s.insert({-deg[A], A});
	s.insert({-deg[B], B});
}

int CountCritical() {
	ans = 0;
	vec.clear();
	if (g2) {
		set <pair <int, int> > :: iterator it = s.begin();
		for (int i = 0; i < 4; i++) {
			if (it == s.end()) {
				break;
			}
			int v = (*it).second;
			check(v);
			if (deg[v] < 4) {
				for (auto u : adj[v]) {
					check(u);
				}
			}
		}
		for (auto x : vec) {
			b[x] = false;
		}
		return ans;
	}
	else {
		int x = f(n + 1);
		if (x == -1) {
			return 0;
		}
		if (x == 0) {
			return n;
		}
		return x;
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 21 ms 24172 KB Output is correct
3 Correct 22 ms 24300 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 22 ms 24172 KB Output is correct
6 Correct 22 ms 24300 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Incorrect 19 ms 24172 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1534 ms 67436 KB Output is correct
2 Execution timed out 4067 ms 90408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 21 ms 24172 KB Output is correct
3 Correct 22 ms 24300 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 22 ms 24172 KB Output is correct
6 Correct 22 ms 24300 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Incorrect 19 ms 24172 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 21 ms 24172 KB Output is correct
3 Correct 22 ms 24300 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 22 ms 24172 KB Output is correct
6 Correct 22 ms 24300 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Incorrect 19 ms 24172 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 21 ms 24172 KB Output is correct
3 Correct 22 ms 24300 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 22 ms 24172 KB Output is correct
6 Correct 22 ms 24300 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Incorrect 19 ms 24172 KB Output isn't correct
9 Halted 0 ms 0 KB -