Submission #546145

#	Time	Username	Problem	Language	Result	Execution time	Memory
546145		keta_tsimakuridze	Parachute rings (IOI12_rings)	C++17	0 / 100	54 ms	51292 KiB

rings

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 100000 + 5;
int n, sz = 0, h[N];
int cycle[7], rem[7], stop = 0, p[N][7];
set<pii> tried[5], 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(h[V[5][a][i]]) {
			sz = h[a] - h[V[5][a][i]] + 1;
			return;
		}
	}
}
void add(int a, int b, int t) {
	if(a == rem[t] || b == rem[t]) return;
	tried[t].erase({V[t][a].size(), a});
	tried[t].erase({V[t][b].size(), b});
	V[t][a].push_back(b); V[t][b].push_back(a);
	tried[t].insert({V[t][a].size(), a});
	tried[t].insert({V[t][b].size(), b});
	if(find(a, t) == find(b, t)) cycle[t] = 1;
	else merge(a, b, t);
	return;	
}
void Link(int a, int b) {
	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(tried[0].size()) {
		add(a, b, 0);
	}
	if(tried[1].size()) {

		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].insert({V[t][i].size(), i});	
}
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(!tried[0].size()) {
			rem[0] = (*--deg.end()).s;
			build(0);
		}
		if((*--tried[0].end()).f <= 2 && !cycle[0]) return 1;
		stop = 1;
		return 0;
	}
	if(!tried[1].size()) {
		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].end()).f <= 2 && !cycle[i]) cn++;
	}
	return cn;
}

Compilation message (stderr)

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: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31