oj.uz

Submission #526660

# Submission time Handle Problem Language Result Execution time Memory
526660 2022-02-15T23:10:27 Z jwvg0425 Parachute rings (IOI12_rings) C++17
37 / 100
 1138 ms 107400 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 par[1000005];
int backStMax;
int backEdMin;
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;

	for (auto& e : edge[x])
	{
		if (order[e] == 0)
		{
			par[e] = x;
			dfs(e);
		}
		else if (e != par[x] && order[e] < order[x])
		{
			backStMax = max(backStMax, order[e]);
			backEdMin = min(backEdMin, order[x]);
		}
	}
}

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

int solve(int x)
{
	s.clear();
	backStMax = 0;
	backEdMin = 987654321;
	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 (cnt[3] == 0 && order[si] >= backStMax && order[si] <= backEdMin)
			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] = 0;
		par[i] = -1;
	}

	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 11 ms 23756 KB Output is correct
2 Correct 13 ms 23944 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 14 ms 24268 KB Output is correct
7 Correct 13 ms 23836 KB Output is correct
8 Correct 13 ms 23944 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 13 ms 24096 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 51052 KB Output is correct
2 Correct 743 ms 66376 KB Output is correct
3 Correct 1108 ms 90308 KB Output is correct
4 Correct 948 ms 77032 KB Output is correct
5 Correct 985 ms 77760 KB Output is correct
6 Correct 1138 ms 107400 KB Output is correct
7 Correct 1060 ms 87684 KB Output is correct
8 Correct 872 ms 73388 KB Output is correct
9 Correct 970 ms 77380 KB Output is correct
10 Correct 538 ms 77708 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 13 ms 23944 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 14 ms 24268 KB Output is correct
7 Correct 13 ms 23836 KB Output is correct
8 Correct 13 ms 23944 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 13 ms 24096 KB Output is correct
11 Incorrect 21 ms 24080 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 13 ms 23944 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 14 ms 24268 KB Output is correct
7 Correct 13 ms 23836 KB Output is correct
8 Correct 13 ms 23944 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 13 ms 24096 KB Output is correct
11 Incorrect 21 ms 24080 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 13 ms 23944 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23936 KB Output is correct
6 Correct 14 ms 24268 KB Output is correct
7 Correct 13 ms 23836 KB Output is correct
8 Correct 13 ms 23944 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 13 ms 24096 KB Output is correct
11 Correct 361 ms 51052 KB Output is correct
12 Correct 743 ms 66376 KB Output is correct
13 Correct 1108 ms 90308 KB Output is correct
14 Correct 948 ms 77032 KB Output is correct
15 Correct 985 ms 77760 KB Output is correct
16 Correct 1138 ms 107400 KB Output is correct
17 Correct 1060 ms 87684 KB Output is correct
18 Correct 872 ms 73388 KB Output is correct
19 Correct 970 ms 77380 KB Output is correct
20 Correct 538 ms 77708 KB Output is correct
21 Incorrect 21 ms 24080 KB Output isn't correct
22 Halted 0 ms 0 KB -