oj.uz

Submission #74163

# Submission time Handle Problem Language Result Execution time Memory
74163 2018-08-30T10:43:07 Z Bruteforceman Parachute rings (IOI12_rings) C++11
100 / 100
 3944 ms 146500 KB 
#include "bits/stdc++.h"
using namespace std;
int N;
struct dsu {
	bool cycle[1000010];
	int head[1000010];
	int tail[1000010];
	int par[1000010];
	int len[1000010];
	int cycle_cnt;
	int cycle_sum;
	bool bad;
	int no_of_nodes;
	int del_node;

	void init (int n) {
		no_of_nodes = n;
		del_node = -1;
		for(int i = 0; i < no_of_nodes; i++) {
			cycle[i] = false;
			head[i] = tail[i] = par[i] = i;
			len[i] = 1;
		}
		cycle_cnt = 0;
		cycle_sum = 0;
		bad = false;
	}
	int root(int x) {
		if(x == par[x]) return par[x];
		return par[x] = root(par[x]);
	}
	void add(int x, int y) {
		if(del_node == x || del_node == y) return ; 
		if(bad) return ;
		int p = root(x);
		int q = root(y);
		if(p == q) {
			if(cycle[p]) {
				bad = true;
				return ;
			} else if(head[p] == x && tail[p] == y) {
				cycle_cnt += 1;
				cycle_sum += len[p];
				cycle[p] = true;
			} else if (head[p] == y && tail[p] == x) {
				cycle_cnt += 1;
				cycle_sum += len[p];
				cycle[p] = true;
			} else {
				bad = true;
				return ;
			}
		} else {
			if(cycle[p] || cycle[q]) {
				bad = true;
				return ;
			}
			par[p] = q;
			len[q] += len[p];
			if(x == head[p]) {
				if(y == head[q]) {
					head[q] = tail[p];
				} else if (y == tail[q]) {
					tail[q] = tail[p];
				} else {
					bad = true;
					return ;
				}
			} else if (x == tail[p]) {
				if(y == head[q]) {
					head[q] = head[p];
				} else if (y == tail[q]) {
					tail[q] = head[p];
				} else {
					bad = true;
					return ;
				}
			} else {
				bad = true;
				return ;
			}
		}
	}
	int count() {
		if(bad) return 0;
		if(cycle_cnt <= 1) {
			if(cycle_cnt == 1) return cycle_sum;
			else return no_of_nodes;
		}
		return 0;
	}
} T[5];
vector <int> g[1000010];
vector <int> l, r;
bool found_cand;

void Init(int N_) {
  N = N_;
  for(int i = 0; i < 5; i++) {
  	T[i].init(N);
  }
  for(int i = 0; i < N; i++) {
  	g[i].clear();
  }
  l.clear(); r.clear();
  found_cand = false;
}



void Link(int A, int B) {
	if(found_cand) {
		for(int i = 1; i <= 4; i++) {
			T[i].add(A, B);
		}
		return ;
	}
	l.emplace_back(A);
	r.emplace_back(B);
	g[A].emplace_back(B);
	g[B].emplace_back(A);
	if(g[A].size() == 3) {
		T[1].del_node = A;
		T[2].del_node = g[A][0];
		T[3].del_node = g[A][1];
		T[4].del_node = g[A][2];
		found_cand = true;
	} else if (g[B].size() == 3) {
		T[1].del_node = B;
		T[2].del_node = g[B][0];
		T[3].del_node = g[B][1];
		T[4].del_node = g[B][2];	
		found_cand = true;
	} else {
		T[0].add(A, B);
	}
	if(found_cand) {
		for(int i = 0; i < (int)l.size(); i++) {
			Link(l[i], r[i]);
		}
	}
}

int CountCritical() {
	if(found_cand) {
		int ans = 0;
		for(int i = 1; i <= 4; i++) {
			if(T[i].cycle_cnt == 0 && !T[i].bad) {
				++ans;
			}
 		}
 		return ans;
	}
	return T[0].count();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24056 KB Output is correct
2 Correct 23 ms 24548 KB Output is correct
3 Correct 23 ms 24548 KB Output is correct
4 Correct 22 ms 24548 KB Output is correct
5 Correct 23 ms 24548 KB Output is correct
6 Correct 26 ms 24856 KB Output is correct
7 Correct 22 ms 24856 KB Output is correct
8 Correct 25 ms 24856 KB Output is correct
9 Correct 24 ms 24856 KB Output is correct
10 Correct 25 ms 24856 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 87884 KB Output is correct
2 Correct 1377 ms 107552 KB Output is correct
3 Correct 459 ms 107832 KB Output is correct
4 Correct 1589 ms 146468 KB Output is correct
5 Correct 1560 ms 146500 KB Output is correct
6 Correct 1529 ms 146500 KB Output is correct
7 Correct 413 ms 146500 KB Output is correct
8 Correct 3268 ms 146500 KB Output is correct
9 Correct 3944 ms 146500 KB Output is correct
10 Correct 1109 ms 146500 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24056 KB Output is correct
2 Correct 23 ms 24548 KB Output is correct
3 Correct 23 ms 24548 KB Output is correct
4 Correct 22 ms 24548 KB Output is correct
5 Correct 23 ms 24548 KB Output is correct
6 Correct 26 ms 24856 KB Output is correct
7 Correct 22 ms 24856 KB Output is correct
8 Correct 25 ms 24856 KB Output is correct
9 Correct 24 ms 24856 KB Output is correct
10 Correct 25 ms 24856 KB Output is correct
11 Correct 25 ms 146500 KB Output is correct
12 Correct 28 ms 146500 KB Output is correct
13 Correct 28 ms 146500 KB Output is correct
14 Correct 27 ms 146500 KB Output is correct
15 Correct 26 ms 146500 KB Output is correct
16 Correct 33 ms 146500 KB Output is correct
17 Correct 26 ms 146500 KB Output is correct
18 Correct 32 ms 146500 KB Output is correct
19 Correct 29 ms 146500 KB Output is correct
20 Correct 28 ms 146500 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24056 KB Output is correct
2 Correct 23 ms 24548 KB Output is correct
3 Correct 23 ms 24548 KB Output is correct
4 Correct 22 ms 24548 KB Output is correct
5 Correct 23 ms 24548 KB Output is correct
6 Correct 26 ms 24856 KB Output is correct
7 Correct 22 ms 24856 KB Output is correct
8 Correct 25 ms 24856 KB Output is correct
9 Correct 24 ms 24856 KB Output is correct
10 Correct 25 ms 24856 KB Output is correct
11 Correct 25 ms 146500 KB Output is correct
12 Correct 28 ms 146500 KB Output is correct
13 Correct 28 ms 146500 KB Output is correct
14 Correct 27 ms 146500 KB Output is correct
15 Correct 26 ms 146500 KB Output is correct
16 Correct 33 ms 146500 KB Output is correct
17 Correct 26 ms 146500 KB Output is correct
18 Correct 32 ms 146500 KB Output is correct
19 Correct 29 ms 146500 KB Output is correct
20 Correct 28 ms 146500 KB Output is correct
21 Correct 47 ms 146500 KB Output is correct
22 Correct 66 ms 146500 KB Output is correct
23 Correct 75 ms 146500 KB Output is correct
24 Correct 66 ms 146500 KB Output is correct
25 Correct 42 ms 146500 KB Output is correct
26 Correct 62 ms 146500 KB Output is correct
27 Correct 82 ms 146500 KB Output is correct
28 Correct 62 ms 146500 KB Output is correct
29 Correct 63 ms 146500 KB Output is correct
30 Correct 103 ms 146500 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24056 KB Output is correct
2 Correct 23 ms 24548 KB Output is correct
3 Correct 23 ms 24548 KB Output is correct
4 Correct 22 ms 24548 KB Output is correct
5 Correct 23 ms 24548 KB Output is correct
6 Correct 26 ms 24856 KB Output is correct
7 Correct 22 ms 24856 KB Output is correct
8 Correct 25 ms 24856 KB Output is correct
9 Correct 24 ms 24856 KB Output is correct
10 Correct 25 ms 24856 KB Output is correct
11 Correct 578 ms 87884 KB Output is correct
12 Correct 1377 ms 107552 KB Output is correct
13 Correct 459 ms 107832 KB Output is correct
14 Correct 1589 ms 146468 KB Output is correct
15 Correct 1560 ms 146500 KB Output is correct
16 Correct 1529 ms 146500 KB Output is correct
17 Correct 413 ms 146500 KB Output is correct
18 Correct 3268 ms 146500 KB Output is correct
19 Correct 3944 ms 146500 KB Output is correct
20 Correct 1109 ms 146500 KB Output is correct
21 Correct 25 ms 146500 KB Output is correct
22 Correct 28 ms 146500 KB Output is correct
23 Correct 28 ms 146500 KB Output is correct
24 Correct 27 ms 146500 KB Output is correct
25 Correct 26 ms 146500 KB Output is correct
26 Correct 33 ms 146500 KB Output is correct
27 Correct 26 ms 146500 KB Output is correct
28 Correct 32 ms 146500 KB Output is correct
29 Correct 29 ms 146500 KB Output is correct
30 Correct 28 ms 146500 KB Output is correct
31 Correct 47 ms 146500 KB Output is correct
32 Correct 66 ms 146500 KB Output is correct
33 Correct 75 ms 146500 KB Output is correct
34 Correct 66 ms 146500 KB Output is correct
35 Correct 42 ms 146500 KB Output is correct
36 Correct 62 ms 146500 KB Output is correct
37 Correct 82 ms 146500 KB Output is correct
38 Correct 62 ms 146500 KB Output is correct
39 Correct 63 ms 146500 KB Output is correct
40 Correct 103 ms 146500 KB Output is correct
41 Correct 359 ms 146500 KB Output is correct
42 Correct 1370 ms 146500 KB Output is correct
43 Correct 312 ms 146500 KB Output is correct
44 Correct 385 ms 146500 KB Output is correct
45 Correct 722 ms 146500 KB Output is correct
46 Correct 998 ms 146500 KB Output is correct
47 Correct 1335 ms 146500 KB Output is correct
48 Correct 381 ms 146500 KB Output is correct
49 Correct 1006 ms 146500 KB Output is correct
50 Correct 1085 ms 146500 KB Output is correct
51 Correct 330 ms 146500 KB Output is correct
52 Correct 361 ms 146500 KB Output is correct
53 Correct 331 ms 146500 KB Output is correct
54 Correct 2037 ms 146500 KB Output is correct
55 Correct 719 ms 146500 KB Output is correct