oj.uz

Submission #63418

# Submission time Handle Problem Language Result Execution time Memory
63418 2018-08-01T18:32:02 Z zadrga Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 229012 KB 
// 19.44

#include <bits/stdc++.h>

using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 1000111
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 

struct DSU{
	bool over;
	int n, owner, max_degree, type;
	set<int> cycles;
	int deg_comp[maxn][4];
	int deg[maxn];
	int sz[maxn];
	int root[maxn];

	int rooting(int x){
		if(root[x] == x)
			return x;
		return root[x] = rooting(root[x]);
	}

	void addEdge(int a, int b){
		if(a == owner || b == owner || over == 1)
			return;

		int ra = rooting(a);
		int rb = rooting(b);

		deg_comp[ra][deg[a]]--;
		deg[a]++; deg[a] = min(deg[a], 3);
		deg_comp[ra][deg[a]]++;

		deg_comp[rb][deg[b]]--;
		deg[b]++; deg[b] = min(deg[b], 3);
		deg_comp[rb][deg[b]]++;

		max_degree = max(max_degree, max(deg[a], deg[b]));

		if(ra != rb){
			root[rb] = ra;
			sz[ra] += sz[rb];
			for(int i = 0; i < 4; i++){
				deg_comp[ra][i] += deg_comp[rb][i];
				deg_comp[rb][i] = 0;
			}
		}

		if(ra == rb)
			cycles.insert(ra);
	}

	void init(int nn, int x, int t, vector<pii> &edge){
		n = nn;
		owner = x;
		cycles.clear();
		max_degree = over = 0;
		type = t;
		memset(deg_comp, 0, sizeof(deg));
		for(int i = 0; i < maxn; i++){
			root[i] = i;
			deg[i] = 0;
			sz[i] = 1;
		}

		for(pii v : edge)
			addEdge(v.fi, v.se);
	}

	int getAns(){
		if(max_degree >= 3){
			over = 1;
			return 0;
		}

		if(type == 2){
			if(max_degree <= 1)
				return n;

			if(max_degree == 2){
				if(cycles.size() == 0)
					return n;

				if(cycles.size() > 1){
					over = 1;
					return 0;
				}

				if(cycles.size() == 1)
					return sz[*cycles.begin()];
			}
		}

		if(type == 3 || type == 4){
			if(cycles.size() > 0){
				over = 1;
				return 0;
			}

			return 1;	
		}
	}
} dsu[6];
 



bool start[6];
int deg[maxn], num[5], ind[5], n;
vector<pii> edge;
vector<int> adj[maxn];
pii cur_range;
int all_max_degree;


void Init(int N){
	n = N;
	all_max_degree = 0;
	dsu[0].init(n, -1, 2, edge);
	memset(ind, -1, sizeof(ind));
	memset(deg, 0, sizeof(deg));
	num[0] = n;
	start[0] = 1;
	cur_range = mp(0, 0);
}
 
void Link(int A, int B){
	adj[A].pb(B);
	adj[B].pb(A);

	num[deg[A]]--;
	deg[A]++; deg[A] = min(deg[A], 4);
	num[deg[A]]++;

	if(ind[deg[A]] == -1)
		ind[deg[A]] = A;

	num[deg[B]]--;
	deg[B]++; deg[B] = min(deg[B], 4);
	num[deg[B]]++;

	if(ind[deg[B]] == -1)
		ind[deg[B]] = B;

	all_max_degree = max(all_max_degree, max(deg[A], deg[B]));

	if(all_max_degree == 3){
		cur_range = mp(1, 4);
		if(!start[1]){
			start[1] = 1;
			int cnt = 1;
			dsu[cnt++].init(n, ind[3], 3, edge);
			for(int v : adj[ind[3]])
				dsu[cnt++].init(n, v, 3, edge);
		}
	}

	if(all_max_degree == 4){
		cur_range = mp(5, 5);
		if(!start[5]){
			start[5] = 1;
			dsu[5].init(n, ind[4], 4, edge);
		}
	}

//	cout << "deg : " << all_max_degree << endl;

	edge.pb(mp(A, B));
	for(int i = cur_range.fi; i <= cur_range.se; i++)
		dsu[i].addEdge(A, B);
}
 
int CountCritical(){ 
	int ret = 0;
	for(int i = cur_range.fi; i <= cur_range.se; i++)
		ret += dsu[i].getAns();
	return ret;
}

Compilation message

rings.cpp: In member function 'int DSU::getAns()':
rings.cpp:114:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43512 KB Output is correct
2 Correct 105 ms 122100 KB Output is correct
3 Correct 109 ms 122100 KB Output is correct
4 Correct 41 ms 122100 KB Output is correct
5 Correct 41 ms 122100 KB Output is correct
6 Correct 42 ms 122100 KB Output is correct
7 Correct 93 ms 122100 KB Output is correct
8 Correct 41 ms 122100 KB Output is correct
9 Correct 96 ms 122100 KB Output is correct
10 Correct 94 ms 122100 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 122100 KB Output is correct
2 Correct 2406 ms 204908 KB Output is correct
3 Correct 2143 ms 229012 KB Output is correct
4 Correct 2103 ms 229012 KB Output is correct
5 Correct 2188 ms 229012 KB Output is correct
6 Correct 2142 ms 229012 KB Output is correct
7 Correct 2168 ms 229012 KB Output is correct
8 Execution timed out 4043 ms 229012 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43512 KB Output is correct
2 Correct 105 ms 122100 KB Output is correct
3 Correct 109 ms 122100 KB Output is correct
4 Correct 41 ms 122100 KB Output is correct
5 Correct 41 ms 122100 KB Output is correct
6 Correct 42 ms 122100 KB Output is correct
7 Correct 93 ms 122100 KB Output is correct
8 Correct 41 ms 122100 KB Output is correct
9 Correct 96 ms 122100 KB Output is correct
10 Correct 94 ms 122100 KB Output is correct
11 Correct 107 ms 229012 KB Output is correct
12 Correct 109 ms 229012 KB Output is correct
13 Correct 108 ms 229012 KB Output is correct
14 Correct 114 ms 229012 KB Output is correct
15 Correct 105 ms 229012 KB Output is correct
16 Correct 43 ms 229012 KB Output is correct
17 Correct 94 ms 229012 KB Output is correct
18 Correct 112 ms 229012 KB Output is correct
19 Correct 46 ms 229012 KB Output is correct
20 Correct 96 ms 229012 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43512 KB Output is correct
2 Correct 105 ms 122100 KB Output is correct
3 Correct 109 ms 122100 KB Output is correct
4 Correct 41 ms 122100 KB Output is correct
5 Correct 41 ms 122100 KB Output is correct
6 Correct 42 ms 122100 KB Output is correct
7 Correct 93 ms 122100 KB Output is correct
8 Correct 41 ms 122100 KB Output is correct
9 Correct 96 ms 122100 KB Output is correct
10 Correct 94 ms 122100 KB Output is correct
11 Correct 107 ms 229012 KB Output is correct
12 Correct 109 ms 229012 KB Output is correct
13 Correct 108 ms 229012 KB Output is correct
14 Correct 114 ms 229012 KB Output is correct
15 Correct 105 ms 229012 KB Output is correct
16 Correct 43 ms 229012 KB Output is correct
17 Correct 94 ms 229012 KB Output is correct
18 Correct 112 ms 229012 KB Output is correct
19 Correct 46 ms 229012 KB Output is correct
20 Correct 96 ms 229012 KB Output is correct
21 Correct 68 ms 229012 KB Output is correct
22 Correct 76 ms 229012 KB Output is correct
23 Correct 89 ms 229012 KB Output is correct
24 Correct 152 ms 229012 KB Output is correct
25 Correct 118 ms 229012 KB Output is correct
26 Correct 158 ms 229012 KB Output is correct
27 Correct 102 ms 229012 KB Output is correct
28 Correct 145 ms 229012 KB Output is correct
29 Correct 144 ms 229012 KB Output is correct
30 Correct 113 ms 229012 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 43512 KB Output is correct
2 Correct 105 ms 122100 KB Output is correct
3 Correct 109 ms 122100 KB Output is correct
4 Correct 41 ms 122100 KB Output is correct
5 Correct 41 ms 122100 KB Output is correct
6 Correct 42 ms 122100 KB Output is correct
7 Correct 93 ms 122100 KB Output is correct
8 Correct 41 ms 122100 KB Output is correct
9 Correct 96 ms 122100 KB Output is correct
10 Correct 94 ms 122100 KB Output is correct
11 Correct 743 ms 122100 KB Output is correct
12 Correct 2406 ms 204908 KB Output is correct
13 Correct 2143 ms 229012 KB Output is correct
14 Correct 2103 ms 229012 KB Output is correct
15 Correct 2188 ms 229012 KB Output is correct
16 Correct 2142 ms 229012 KB Output is correct
17 Correct 2168 ms 229012 KB Output is correct
18 Execution timed out 4043 ms 229012 KB Time limit exceeded
19 Halted 0 ms 0 KB -