oj.uz

Submission #546163

# Submission time Handle Problem Language Result Execution time Memory
546163 2022-04-06T14:59:04 Z keta_tsimakuridze Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 249192 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];
set<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;
	}
	deg.insert({0, 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][b].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;
	deg.erase({V[5][a].size(), a});
	deg.erase({V[5][b].size(), b});
	V[5][a].push_back(b); V[5][b].push_back(a);
	deg.insert({V[5][a].size(), a});
	deg.insert({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.end()).f <= 2) return n;
	if((*--deg.end()).f <= 2) return sz;
	
	if((*--deg.end()).f >= 4) {
		if(!built[0]) {
			rem[0] = (*--deg.end()).s;
			build(0);
		}
		if(tried[0] <= 2 && !cycle[0]) return 1;
		stop = 1;
		return 0;
	}
	if(!built[1]) {
		rem[1] = (*--deg.end()).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:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < V[5][a].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void build(int)':
rings.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int j = 0; j < V[5][i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   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 74 ms 164696 KB Output is correct
2 Correct 81 ms 165288 KB Output is correct
3 Correct 83 ms 165408 KB Output is correct
4 Correct 76 ms 164808 KB Output is correct
5 Correct 80 ms 165068 KB Output is correct
6 Correct 83 ms 165460 KB Output is correct
7 Correct 81 ms 165104 KB Output is correct
8 Correct 83 ms 165060 KB Output is correct
9 Correct 85 ms 165804 KB Output is correct
10 Correct 87 ms 165884 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1917 ms 219888 KB Output is correct
2 Execution timed out 4075 ms 249192 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 164696 KB Output is correct
2 Correct 81 ms 165288 KB Output is correct
3 Correct 83 ms 165408 KB Output is correct
4 Correct 76 ms 164808 KB Output is correct
5 Correct 80 ms 165068 KB Output is correct
6 Correct 83 ms 165460 KB Output is correct
7 Correct 81 ms 165104 KB Output is correct
8 Correct 83 ms 165060 KB Output is correct
9 Correct 85 ms 165804 KB Output is correct
10 Correct 87 ms 165884 KB Output is correct
11 Incorrect 83 ms 165504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 164696 KB Output is correct
2 Correct 81 ms 165288 KB Output is correct
3 Correct 83 ms 165408 KB Output is correct
4 Correct 76 ms 164808 KB Output is correct
5 Correct 80 ms 165068 KB Output is correct
6 Correct 83 ms 165460 KB Output is correct
7 Correct 81 ms 165104 KB Output is correct
8 Correct 83 ms 165060 KB Output is correct
9 Correct 85 ms 165804 KB Output is correct
10 Correct 87 ms 165884 KB Output is correct
11 Incorrect 83 ms 165504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 164696 KB Output is correct
2 Correct 81 ms 165288 KB Output is correct
3 Correct 83 ms 165408 KB Output is correct
4 Correct 76 ms 164808 KB Output is correct
5 Correct 80 ms 165068 KB Output is correct
6 Correct 83 ms 165460 KB Output is correct
7 Correct 81 ms 165104 KB Output is correct
8 Correct 83 ms 165060 KB Output is correct
9 Correct 85 ms 165804 KB Output is correct
10 Correct 87 ms 165884 KB Output is correct
11 Correct 1917 ms 219888 KB Output is correct
12 Execution timed out 4075 ms 249192 KB Time limit exceeded
13 Halted 0 ms 0 KB -