oj.uz

Submission #546165

# Submission time Handle Problem Language Result Execution time Memory
546165 2022-04-06T15:02:50 Z keta_tsimakuridze Parachute rings (IOI12_rings) C++14
20 / 100
 1571 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[6] , rem[7], stop = 0, p[N][7], built[N];
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]) {
		built[0] = 1;
		add(a, b, 0);
	}
	if(built[1]) {
		built[1] = 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]) {
			rem[0] = deg.s;
			build(0);
		}
		if(tried[0] <= 2 && !cycle[0]) return 1;
		stop = 1;
		return 0;
	}
	if(!built[1]) {
		rem[1] = deg.s; 
		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:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int j = 0; j < V[5][i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   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 83 ms 164648 KB Output is correct
2 Correct 82 ms 165096 KB Output is correct
3 Correct 79 ms 165056 KB Output is correct
4 Correct 79 ms 164684 KB Output is correct
5 Correct 76 ms 164940 KB Output is correct
6 Correct 86 ms 165336 KB Output is correct
7 Correct 77 ms 164940 KB Output is correct
8 Correct 77 ms 164976 KB Output is correct
9 Correct 82 ms 165572 KB Output is correct
10 Correct 87 ms 165564 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 195240 KB Output is correct
2 Correct 1235 ms 236664 KB Output is correct
3 Correct 603 ms 211200 KB Output is correct
4 Correct 998 ms 224984 KB Output is correct
5 Correct 1006 ms 228540 KB Output is correct
6 Correct 1148 ms 262144 KB Output is correct
7 Correct 1571 ms 249468 KB Output is correct
8 Runtime error 1382 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164648 KB Output is correct
2 Correct 82 ms 165096 KB Output is correct
3 Correct 79 ms 165056 KB Output is correct
4 Correct 79 ms 164684 KB Output is correct
5 Correct 76 ms 164940 KB Output is correct
6 Correct 86 ms 165336 KB Output is correct
7 Correct 77 ms 164940 KB Output is correct
8 Correct 77 ms 164976 KB Output is correct
9 Correct 82 ms 165572 KB Output is correct
10 Correct 87 ms 165564 KB Output is correct
11 Incorrect 80 ms 165272 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164648 KB Output is correct
2 Correct 82 ms 165096 KB Output is correct
3 Correct 79 ms 165056 KB Output is correct
4 Correct 79 ms 164684 KB Output is correct
5 Correct 76 ms 164940 KB Output is correct
6 Correct 86 ms 165336 KB Output is correct
7 Correct 77 ms 164940 KB Output is correct
8 Correct 77 ms 164976 KB Output is correct
9 Correct 82 ms 165572 KB Output is correct
10 Correct 87 ms 165564 KB Output is correct
11 Incorrect 80 ms 165272 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164648 KB Output is correct
2 Correct 82 ms 165096 KB Output is correct
3 Correct 79 ms 165056 KB Output is correct
4 Correct 79 ms 164684 KB Output is correct
5 Correct 76 ms 164940 KB Output is correct
6 Correct 86 ms 165336 KB Output is correct
7 Correct 77 ms 164940 KB Output is correct
8 Correct 77 ms 164976 KB Output is correct
9 Correct 82 ms 165572 KB Output is correct
10 Correct 87 ms 165564 KB Output is correct
11 Correct 397 ms 195240 KB Output is correct
12 Correct 1235 ms 236664 KB Output is correct
13 Correct 603 ms 211200 KB Output is correct
14 Correct 998 ms 224984 KB Output is correct
15 Correct 1006 ms 228540 KB Output is correct
16 Correct 1148 ms 262144 KB Output is correct
17 Correct 1571 ms 249468 KB Output is correct
18 Runtime error 1382 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -