oj.uz

Submission #526585

# Submission time Handle Problem Language Result Execution time Memory
526585 2022-02-15T10:49:15 Z jwvg0425 Parachute rings (IOI12_rings) C++17
37 / 100
 1263 ms 110316 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]++;
		}

		if (e != par[x])
			up[x] = min(up[x], up[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)]++;
	}

	return res;
}

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

	t = 0;

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

		int now = solve(i);

		if (now == 0)
		{
			res += s.size();
			continue;
		}

		cx.push_back(now);
	}

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

	if (cx.empty())
		return res;

	return cx[0];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23904 KB Output is correct
2 Correct 14 ms 24084 KB Output is correct
3 Correct 15 ms 24196 KB Output is correct
4 Correct 16 ms 23812 KB Output is correct
5 Correct 13 ms 24024 KB Output is correct
6 Correct 14 ms 24356 KB Output is correct
7 Correct 14 ms 23896 KB Output is correct
8 Correct 15 ms 24092 KB Output is correct
9 Correct 14 ms 24152 KB Output is correct
10 Correct 14 ms 24184 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 53016 KB Output is correct
2 Correct 801 ms 63400 KB Output is correct
3 Correct 1263 ms 90400 KB Output is correct
4 Correct 1056 ms 72540 KB Output is correct
5 Correct 1052 ms 73684 KB Output is correct
6 Correct 1263 ms 110316 KB Output is correct
7 Correct 1231 ms 89340 KB Output is correct
8 Correct 1039 ms 70796 KB Output is correct
9 Correct 1117 ms 74752 KB Output is correct
10 Correct 554 ms 76496 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23904 KB Output is correct
2 Correct 14 ms 24084 KB Output is correct
3 Correct 15 ms 24196 KB Output is correct
4 Correct 16 ms 23812 KB Output is correct
5 Correct 13 ms 24024 KB Output is correct
6 Correct 14 ms 24356 KB Output is correct
7 Correct 14 ms 23896 KB Output is correct
8 Correct 15 ms 24092 KB Output is correct
9 Correct 14 ms 24152 KB Output is correct
10 Correct 14 ms 24184 KB Output is correct
11 Correct 24 ms 24080 KB Output is correct
12 Incorrect 60 ms 24948 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23904 KB Output is correct
2 Correct 14 ms 24084 KB Output is correct
3 Correct 15 ms 24196 KB Output is correct
4 Correct 16 ms 23812 KB Output is correct
5 Correct 13 ms 24024 KB Output is correct
6 Correct 14 ms 24356 KB Output is correct
7 Correct 14 ms 23896 KB Output is correct
8 Correct 15 ms 24092 KB Output is correct
9 Correct 14 ms 24152 KB Output is correct
10 Correct 14 ms 24184 KB Output is correct
11 Correct 24 ms 24080 KB Output is correct
12 Incorrect 60 ms 24948 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23904 KB Output is correct
2 Correct 14 ms 24084 KB Output is correct
3 Correct 15 ms 24196 KB Output is correct
4 Correct 16 ms 23812 KB Output is correct
5 Correct 13 ms 24024 KB Output is correct
6 Correct 14 ms 24356 KB Output is correct
7 Correct 14 ms 23896 KB Output is correct
8 Correct 15 ms 24092 KB Output is correct
9 Correct 14 ms 24152 KB Output is correct
10 Correct 14 ms 24184 KB Output is correct
11 Correct 416 ms 53016 KB Output is correct
12 Correct 801 ms 63400 KB Output is correct
13 Correct 1263 ms 90400 KB Output is correct
14 Correct 1056 ms 72540 KB Output is correct
15 Correct 1052 ms 73684 KB Output is correct
16 Correct 1263 ms 110316 KB Output is correct
17 Correct 1231 ms 89340 KB Output is correct
18 Correct 1039 ms 70796 KB Output is correct
19 Correct 1117 ms 74752 KB Output is correct
20 Correct 554 ms 76496 KB Output is correct
21 Correct 24 ms 24080 KB Output is correct
22 Incorrect 60 ms 24948 KB Output isn't correct
23 Halted 0 ms 0 KB -