oj.uz

Submission #526587

# Submission time Handle Problem Language Result Execution time Memory
526587 2022-02-15T11:17:53 Z jwvg0425 Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 111116 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int n;

void Init(int n_)
{
	n = n_;
}

vector<int> edge[1000005];
int order[1000005];
int t = 0;
int comp[1000005];
int par[1000005];
int up[1000005];
vector<int> s;

void Link(int a, int b)
{
	edge[a].push_back(b);
	edge[b].push_back(a);
}

void dfs(int x)
{
	s.push_back(x);
	t++;
	order[x] = t;
	up[x] = order[x];
	comp[x] = s.size() == 1 ? 0 : 1;

	for (auto& e : edge[x])
	{
		if (order[e] == 0)
		{
			par[e] = x;
			dfs(e);

			if (up[e] >= order[x])
				comp[x]++;

			up[x] = min(up[x], up[e]);
		}
		else
		{
			up[x] = min(up[x], order[e]);
		}
	}
}

int getDegree(int x, int off = 0)
{
	return min((int)edge[x].size() - off, 3);
}

int solve(int x)
{
	s.clear();
	dfs(x);

	vector<int> cnt(6);

	for (auto& si : s)
		cnt[getDegree(si)]++;

	if (cnt[0] != 0 || (cnt[1] == 2 && cnt[3] == 0))
		return 0;

	int res = 0;

	for (auto& si : s)
	{
		cnt[getDegree(si)]--;
		for (auto& e : edge[si])
		{
			cnt[getDegree(e)]--;
			cnt[getDegree(e, 1)]++;
		}

		if (comp[si] * 2 == cnt[1] + cnt[0] * 2 && cnt[3] == 0)
			res++;

		for (auto& e : edge[si])
		{
			cnt[getDegree(e)]++;
			cnt[getDegree(e, 1)]--;
		}
		cnt[getDegree(si)]++;
	}

	if (res == 0)
		return -1;

	return res;
}

int k = 0;
int CountCritical()
{
	k++;
	for (int i = 0; i < n; i++)
	{
		order[i] = comp[i] = 0;
		par[i] = -1;
		up[i] = 987654321;
	}

	t = 0;

	vector<int> cx;
	for (int i = 0; i < n && cx.size() < 2; i++)
	{
		if (order[i] != 0)
			continue;

		int now = solve(i);

		if (now == 0)
			continue;

		if (now == -1)
			return 0;

		cx.push_back(now);
	}

	if (cx.size() >= 2)
		return 0;

	if (cx.empty())
		return n;

	return cx[0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23696 KB Output is correct
2 Correct 14 ms 24136 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 13 ms 23812 KB Output is correct
5 Correct 15 ms 24064 KB Output is correct
6 Correct 15 ms 24476 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24004 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 49052 KB Output is correct
2 Correct 778 ms 62644 KB Output is correct
3 Correct 1153 ms 89912 KB Output is correct
4 Correct 993 ms 72264 KB Output is correct
5 Correct 1018 ms 74164 KB Output is correct
6 Correct 1208 ms 111116 KB Output is correct
7 Correct 1142 ms 87584 KB Output is correct
8 Correct 943 ms 69060 KB Output is correct
9 Correct 1044 ms 72920 KB Output is correct
10 Correct 529 ms 74752 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23696 KB Output is correct
2 Correct 14 ms 24136 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 13 ms 23812 KB Output is correct
5 Correct 15 ms 24064 KB Output is correct
6 Correct 15 ms 24476 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24004 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct
11 Correct 24 ms 24076 KB Output is correct
12 Correct 64 ms 24948 KB Output is correct
13 Correct 61 ms 24888 KB Output is correct
14 Correct 63 ms 24188 KB Output is correct
15 Correct 105 ms 24324 KB Output is correct
16 Correct 56 ms 24400 KB Output is correct
17 Correct 20 ms 24408 KB Output is correct
18 Correct 23 ms 24576 KB Output is correct
19 Correct 57 ms 24336 KB Output is correct
20 Correct 56 ms 24444 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23696 KB Output is correct
2 Correct 14 ms 24136 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 13 ms 23812 KB Output is correct
5 Correct 15 ms 24064 KB Output is correct
6 Correct 15 ms 24476 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24004 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct
11 Correct 24 ms 24076 KB Output is correct
12 Correct 64 ms 24948 KB Output is correct
13 Correct 61 ms 24888 KB Output is correct
14 Correct 63 ms 24188 KB Output is correct
15 Correct 105 ms 24324 KB Output is correct
16 Correct 56 ms 24400 KB Output is correct
17 Correct 20 ms 24408 KB Output is correct
18 Correct 23 ms 24576 KB Output is correct
19 Correct 57 ms 24336 KB Output is correct
20 Correct 56 ms 24444 KB Output is correct
21 Execution timed out 4083 ms 24924 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23696 KB Output is correct
2 Correct 14 ms 24136 KB Output is correct
3 Correct 14 ms 24072 KB Output is correct
4 Correct 13 ms 23812 KB Output is correct
5 Correct 15 ms 24064 KB Output is correct
6 Correct 15 ms 24476 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24004 KB Output is correct
9 Correct 14 ms 24140 KB Output is correct
10 Correct 13 ms 24140 KB Output is correct
11 Correct 384 ms 49052 KB Output is correct
12 Correct 778 ms 62644 KB Output is correct
13 Correct 1153 ms 89912 KB Output is correct
14 Correct 993 ms 72264 KB Output is correct
15 Correct 1018 ms 74164 KB Output is correct
16 Correct 1208 ms 111116 KB Output is correct
17 Correct 1142 ms 87584 KB Output is correct
18 Correct 943 ms 69060 KB Output is correct
19 Correct 1044 ms 72920 KB Output is correct
20 Correct 529 ms 74752 KB Output is correct
21 Correct 24 ms 24076 KB Output is correct
22 Correct 64 ms 24948 KB Output is correct
23 Correct 61 ms 24888 KB Output is correct
24 Correct 63 ms 24188 KB Output is correct
25 Correct 105 ms 24324 KB Output is correct
26 Correct 56 ms 24400 KB Output is correct
27 Correct 20 ms 24408 KB Output is correct
28 Correct 23 ms 24576 KB Output is correct
29 Correct 57 ms 24336 KB Output is correct
30 Correct 56 ms 24444 KB Output is correct
31 Execution timed out 4083 ms 24924 KB Time limit exceeded
32 Halted 0 ms 0 KB -