oj.uz

Submission #526584

# Submission time Handle Problem Language Result Execution time Memory
526584 2022-02-15T10:46:53 Z jwvg0425 Parachute rings (IOI12_rings) C++17
37 / 100
 1424 ms 122592 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[3] == 0 && cnt[1] != 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 17 ms 23828 KB Output is correct
2 Correct 21 ms 23984 KB Output is correct
3 Correct 22 ms 24096 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 16 ms 24128 KB Output is correct
6 Correct 29 ms 24368 KB Output is correct
7 Correct 17 ms 23912 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 18 ms 24228 KB Output is correct
10 Correct 16 ms 24208 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 55176 KB Output is correct
2 Correct 1002 ms 72692 KB Output is correct
3 Correct 1256 ms 101732 KB Output is correct
4 Correct 1261 ms 84784 KB Output is correct
5 Correct 1297 ms 85768 KB Output is correct
6 Correct 1424 ms 122592 KB Output is correct
7 Correct 1212 ms 98744 KB Output is correct
8 Correct 973 ms 80908 KB Output is correct
9 Correct 1083 ms 85444 KB Output is correct
10 Correct 548 ms 86528 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23828 KB Output is correct
2 Correct 21 ms 23984 KB Output is correct
3 Correct 22 ms 24096 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 16 ms 24128 KB Output is correct
6 Correct 29 ms 24368 KB Output is correct
7 Correct 17 ms 23912 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 18 ms 24228 KB Output is correct
10 Correct 16 ms 24208 KB Output is correct
11 Correct 24 ms 24096 KB Output is correct
12 Incorrect 64 ms 24952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23828 KB Output is correct
2 Correct 21 ms 23984 KB Output is correct
3 Correct 22 ms 24096 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 16 ms 24128 KB Output is correct
6 Correct 29 ms 24368 KB Output is correct
7 Correct 17 ms 23912 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 18 ms 24228 KB Output is correct
10 Correct 16 ms 24208 KB Output is correct
11 Correct 24 ms 24096 KB Output is correct
12 Incorrect 64 ms 24952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23828 KB Output is correct
2 Correct 21 ms 23984 KB Output is correct
3 Correct 22 ms 24096 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 16 ms 24128 KB Output is correct
6 Correct 29 ms 24368 KB Output is correct
7 Correct 17 ms 23912 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 18 ms 24228 KB Output is correct
10 Correct 16 ms 24208 KB Output is correct
11 Correct 511 ms 55176 KB Output is correct
12 Correct 1002 ms 72692 KB Output is correct
13 Correct 1256 ms 101732 KB Output is correct
14 Correct 1261 ms 84784 KB Output is correct
15 Correct 1297 ms 85768 KB Output is correct
16 Correct 1424 ms 122592 KB Output is correct
17 Correct 1212 ms 98744 KB Output is correct
18 Correct 973 ms 80908 KB Output is correct
19 Correct 1083 ms 85444 KB Output is correct
20 Correct 548 ms 86528 KB Output is correct
21 Correct 24 ms 24096 KB Output is correct
22 Incorrect 64 ms 24952 KB Output isn't correct
23 Halted 0 ms 0 KB -