oj.uz

Submission #63420

# Submission time Handle Problem Language Result Execution time Memory
63420 2018-08-01T18:37:12 Z zadrga Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 225624 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);

		if(max_degree == 3 || cycles.size() > 1)
			over = 1;

		if(type >= 3 && cycles.size() == 1)
			over = 1;
	}

	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(over)
			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)
					return sz[*cycles.begin()];
			}
		}

		if(type == 3 || type == 4)
			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:107: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 38 ms 43512 KB Output is correct
2 Correct 107 ms 121972 KB Output is correct
3 Correct 106 ms 122196 KB Output is correct
4 Correct 40 ms 122196 KB Output is correct
5 Correct 44 ms 122196 KB Output is correct
6 Correct 47 ms 122196 KB Output is correct
7 Correct 99 ms 122196 KB Output is correct
8 Correct 43 ms 122196 KB Output is correct
9 Correct 94 ms 122196 KB Output is correct
10 Correct 96 ms 122196 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 122196 KB Output is correct
2 Correct 2539 ms 204964 KB Output is correct
3 Correct 1208 ms 225212 KB Output is correct
4 Correct 2148 ms 225212 KB Output is correct
5 Correct 2148 ms 225212 KB Output is correct
6 Correct 2121 ms 225212 KB Output is correct
7 Correct 1220 ms 225624 KB Output is correct
8 Execution timed out 4029 ms 225624 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 43512 KB Output is correct
2 Correct 107 ms 121972 KB Output is correct
3 Correct 106 ms 122196 KB Output is correct
4 Correct 40 ms 122196 KB Output is correct
5 Correct 44 ms 122196 KB Output is correct
6 Correct 47 ms 122196 KB Output is correct
7 Correct 99 ms 122196 KB Output is correct
8 Correct 43 ms 122196 KB Output is correct
9 Correct 94 ms 122196 KB Output is correct
10 Correct 96 ms 122196 KB Output is correct
11 Correct 109 ms 225624 KB Output is correct
12 Correct 111 ms 225624 KB Output is correct
13 Correct 112 ms 225624 KB Output is correct
14 Correct 108 ms 225624 KB Output is correct
15 Correct 109 ms 225624 KB Output is correct
16 Correct 45 ms 225624 KB Output is correct
17 Correct 98 ms 225624 KB Output is correct
18 Correct 110 ms 225624 KB Output is correct
19 Correct 45 ms 225624 KB Output is correct
20 Correct 99 ms 225624 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 43512 KB Output is correct
2 Correct 107 ms 121972 KB Output is correct
3 Correct 106 ms 122196 KB Output is correct
4 Correct 40 ms 122196 KB Output is correct
5 Correct 44 ms 122196 KB Output is correct
6 Correct 47 ms 122196 KB Output is correct
7 Correct 99 ms 122196 KB Output is correct
8 Correct 43 ms 122196 KB Output is correct
9 Correct 94 ms 122196 KB Output is correct
10 Correct 96 ms 122196 KB Output is correct
11 Correct 109 ms 225624 KB Output is correct
12 Correct 111 ms 225624 KB Output is correct
13 Correct 112 ms 225624 KB Output is correct
14 Correct 108 ms 225624 KB Output is correct
15 Correct 109 ms 225624 KB Output is correct
16 Correct 45 ms 225624 KB Output is correct
17 Correct 98 ms 225624 KB Output is correct
18 Correct 110 ms 225624 KB Output is correct
19 Correct 45 ms 225624 KB Output is correct
20 Correct 99 ms 225624 KB Output is correct
21 Correct 64 ms 225624 KB Output is correct
22 Correct 77 ms 225624 KB Output is correct
23 Correct 91 ms 225624 KB Output is correct
24 Correct 194 ms 225624 KB Output is correct
25 Correct 116 ms 225624 KB Output is correct
26 Correct 155 ms 225624 KB Output is correct
27 Correct 105 ms 225624 KB Output is correct
28 Correct 144 ms 225624 KB Output is correct
29 Correct 145 ms 225624 KB Output is correct
30 Correct 111 ms 225624 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 43512 KB Output is correct
2 Correct 107 ms 121972 KB Output is correct
3 Correct 106 ms 122196 KB Output is correct
4 Correct 40 ms 122196 KB Output is correct
5 Correct 44 ms 122196 KB Output is correct
6 Correct 47 ms 122196 KB Output is correct
7 Correct 99 ms 122196 KB Output is correct
8 Correct 43 ms 122196 KB Output is correct
9 Correct 94 ms 122196 KB Output is correct
10 Correct 96 ms 122196 KB Output is correct
11 Correct 759 ms 122196 KB Output is correct
12 Correct 2539 ms 204964 KB Output is correct
13 Correct 1208 ms 225212 KB Output is correct
14 Correct 2148 ms 225212 KB Output is correct
15 Correct 2148 ms 225212 KB Output is correct
16 Correct 2121 ms 225212 KB Output is correct
17 Correct 1220 ms 225624 KB Output is correct
18 Execution timed out 4029 ms 225624 KB Time limit exceeded
19 Halted 0 ms 0 KB -