oj.uz

Submission #546173

# Submission time Handle Problem Language Result Execution time Memory
546173 2022-04-06T15:12:13 Z keta_tsimakuridze Parachute rings (IOI12_rings) C++14
52 / 100
 1587 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 1000000 + 5;
int n, sz = 0, h[N];
int cycle[7],tried[7] , rem[7], stop = 0, p[N][7], built[2];
pii deg;
vector<int> V[7][N];
void Init(int N_) {
  n = N_;
  for(int i = 0; i < n; i++) {
  	for(int t = 0; t < 6; t++) {
  		p[i][t] = i;
	}
  }
}
int find(int a, int t) {
	return (p[a][t] == a ? p[a][t] :  p[a][t] = find(p[a][t], t));	
}
void merge(int a,int b, int t) {
	a = find(a, t); b = find(b, t);
	if(a == b) return;
	p[a][t] = b;
	return;
}
void dfs(int a, int p) {
	h[a] = h[p] + 1;
	for(int i = 0; i < V[5][a].size(); i++) {
		if(V[5][a][i] == p) continue;
		if(sz) return;
		if(h[V[5][a][i]]) { 
			sz = h[a] - h[V[5][a][i]] + 1;
			return;
		} else dfs(V[5][a][i], a);
	}
}
void add(int a, int b, int t) {
	if(a == rem[t] || b == rem[t]) return;
	V[t][a].push_back(b); V[t][b].push_back(a);
	tried[t] = max(tried[t], max((int)V[t][a].size(),(int) V[t][b].size()));
	if(find(a, t) == find(b, t)) cycle[t] = 1;
	else merge(a, b, t);
	return;	
}
void Link(int a, int b) {
	if(stop) return;
	V[5][a].push_back(b); V[5][b].push_back(a);
	deg = max(deg, {(int)V[5][a].size(), a});
	deg = max(deg, {(int)V[5][b].size(), b});
	if(find(a, 5) != find(b, 5)) {
		merge(a, b, 5);
	}
	else {
		if(!cycle[5]) {
			merge(a, b, 5);
			dfs(a, -1);
			cycle[5] = a + 1;
		}
		else if(find(a, 5) != find(cycle[5] - 1, 5)) {
			stop = 1;
		}
	}
	if(built[0]) {
		add(a, b, 0);
	}
	if(built[1]) {
		for(int i = 1; i <= 4; i++) add(a, b, i);
	}
	
}
void build(int t) {
	int u = rem[t];
	for(int i = 0; i < n; i++) {
		if(u == i) continue;
		for(int j = 0; j < V[5][i].size(); j++) {
			int v = V[5][i][j];
			if(v == u || v < i) continue;
			if(find(v, t) == find(i, t)) cycle[t] = 1;
			merge(i, v, t);
			V[t][i].push_back(v); V[t][v].push_back(i);
		}
	}
	for(int i = 0; i < n; i++) tried[t] = max(tried[t], (int)V[t][i].size());	
}
int CountCritical() {
	if(stop) return 0; 
	if(!cycle[5] && deg.f <= 2) return n;
	if(deg.f <= 2) return sz;
	
	if(deg.f >= 4) {
		if(!built[0]) {
			built[0] = 1;
			rem[0] = deg.s;
			build(0);
		}
		if(tried[0] <= 2 && !cycle[0]) return 1;
		stop = 1;
		return 0;
	}
	if(!built[1]) {
		built[1] = 1;
		rem[1] = deg.s; 
		assert(V[5][rem[1]].size() == 3);
		for(int i = 0; i < V[5][rem[1]].size(); i++) {
			rem[i + 2] = V[5][rem[1]][i]; 
		}
		for(int i = 1; i <= 4; i++) {
			build(i);
		}
	}
	int cn = 0;
	for(int i = 1; i <= 4; i++) {
		if(tried[i] <= 2 && !cycle[i]) cn++;
	}
	if(!cn) stop = 1;
	return cn;
}

Compilation message

rings.cpp: In function 'void dfs(int, int)':
rings.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < V[5][a].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void build(int)':
rings.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int j = 0; j < V[5][i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 0; i < V[5][rem[1]].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164688 KB Output is correct
2 Correct 86 ms 165068 KB Output is correct
3 Correct 84 ms 165128 KB Output is correct
4 Correct 91 ms 164660 KB Output is correct
5 Correct 82 ms 164912 KB Output is correct
6 Correct 80 ms 165192 KB Output is correct
7 Correct 81 ms 164892 KB Output is correct
8 Correct 80 ms 164904 KB Output is correct
9 Correct 94 ms 165600 KB Output is correct
10 Correct 79 ms 165580 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 195268 KB Output is correct
2 Correct 1317 ms 236704 KB Output is correct
3 Correct 610 ms 211288 KB Output is correct
4 Correct 970 ms 225008 KB Output is correct
5 Correct 1006 ms 228384 KB Output is correct
6 Correct 1124 ms 256424 KB Output is correct
7 Correct 1587 ms 249444 KB Output is correct
8 Runtime error 1414 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164688 KB Output is correct
2 Correct 86 ms 165068 KB Output is correct
3 Correct 84 ms 165128 KB Output is correct
4 Correct 91 ms 164660 KB Output is correct
5 Correct 82 ms 164912 KB Output is correct
6 Correct 80 ms 165192 KB Output is correct
7 Correct 81 ms 164892 KB Output is correct
8 Correct 80 ms 164904 KB Output is correct
9 Correct 94 ms 165600 KB Output is correct
10 Correct 79 ms 165580 KB Output is correct
11 Correct 85 ms 165668 KB Output is correct
12 Correct 85 ms 166504 KB Output is correct
13 Correct 96 ms 166832 KB Output is correct
14 Correct 80 ms 165300 KB Output is correct
15 Correct 82 ms 165492 KB Output is correct
16 Correct 86 ms 165332 KB Output is correct
17 Correct 88 ms 164972 KB Output is correct
18 Correct 91 ms 165416 KB Output is correct
19 Correct 80 ms 165280 KB Output is correct
20 Correct 88 ms 166460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164688 KB Output is correct
2 Correct 86 ms 165068 KB Output is correct
3 Correct 84 ms 165128 KB Output is correct
4 Correct 91 ms 164660 KB Output is correct
5 Correct 82 ms 164912 KB Output is correct
6 Correct 80 ms 165192 KB Output is correct
7 Correct 81 ms 164892 KB Output is correct
8 Correct 80 ms 164904 KB Output is correct
9 Correct 94 ms 165600 KB Output is correct
10 Correct 79 ms 165580 KB Output is correct
11 Correct 85 ms 165668 KB Output is correct
12 Correct 85 ms 166504 KB Output is correct
13 Correct 96 ms 166832 KB Output is correct
14 Correct 80 ms 165300 KB Output is correct
15 Correct 82 ms 165492 KB Output is correct
16 Correct 86 ms 165332 KB Output is correct
17 Correct 88 ms 164972 KB Output is correct
18 Correct 91 ms 165416 KB Output is correct
19 Correct 80 ms 165280 KB Output is correct
20 Correct 88 ms 166460 KB Output is correct
21 Correct 98 ms 167084 KB Output is correct
22 Correct 101 ms 168524 KB Output is correct
23 Correct 108 ms 169500 KB Output is correct
24 Correct 157 ms 170496 KB Output is correct
25 Correct 109 ms 168704 KB Output is correct
26 Correct 216 ms 179880 KB Output is correct
27 Correct 113 ms 169440 KB Output is correct
28 Correct 97 ms 167584 KB Output is correct
29 Correct 109 ms 168324 KB Output is correct
30 Correct 137 ms 171600 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164688 KB Output is correct
2 Correct 86 ms 165068 KB Output is correct
3 Correct 84 ms 165128 KB Output is correct
4 Correct 91 ms 164660 KB Output is correct
5 Correct 82 ms 164912 KB Output is correct
6 Correct 80 ms 165192 KB Output is correct
7 Correct 81 ms 164892 KB Output is correct
8 Correct 80 ms 164904 KB Output is correct
9 Correct 94 ms 165600 KB Output is correct
10 Correct 79 ms 165580 KB Output is correct
11 Correct 435 ms 195268 KB Output is correct
12 Correct 1317 ms 236704 KB Output is correct
13 Correct 610 ms 211288 KB Output is correct
14 Correct 970 ms 225008 KB Output is correct
15 Correct 1006 ms 228384 KB Output is correct
16 Correct 1124 ms 256424 KB Output is correct
17 Correct 1587 ms 249444 KB Output is correct
18 Runtime error 1414 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -