Submission #760708

#	Time	Username	Problem	Language	Result	Execution time	Memory
760708		NothingXD	Parachute rings (IOI12_rings)	C++17	52 / 100	76 ms	55968 KiB

rings

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, par[10][maxn], cycle;
bool bad[10];
vector<int> g[maxn][10], ver;

int getpar(int idx, int v){
	return (par[idx][v] < 0? v: par[idx][v] = getpar(idx, par[idx][v]));
}

bool merge(int idx, int x, int y){
	int u = getpar(idx, x);
	int v = getpar(idx, y);
	if (u == v) return false;
	par[idx][u] += par[idx][v];
	par[idx][v] = u;
	return true;
}

void Init(int N_) {
	memset(par, -1, sizeof par);
	n = N_;
}

void Link(int A, int B) {
	if (!bad[0]){
		g[A][0].push_back(B);
		g[B][0].push_back(A);
		if (g[A][0].size() == 3){
			bad[0] = true;
			ver.push_back(A);
			for (auto x: g[A][0])ver.push_back(x);
			for (int i = 1; i <= ver.size(); i++){
				for (int j = 0; j < n; j++){
					if (j == ver[i-1]) continue;
					for (auto u: g[j][0]){
						if (u < j || u == ver[i-1]) continue;
						g[j][i].push_back(u);
						g[u][i].push_back(j);
						if (max(g[j][i].size(), g[u][i].size()) > 2 || !merge(i, j, u)) bad[i] = true;
					}
				}
			}
		}
		else if (g[B][0].size() == 3){
			bad[0] = true;
			ver.push_back(B);
			for (auto x: g[B][0])ver.push_back(x);
			for (int i = 1; i <= ver.size(); i++){
				for (int j = 0; j < n; j++){
					if (j == ver[i-1]) continue;
					for (auto u: g[j][0]){
						if (u < j || u == ver[i-1]) continue;
						g[j][i].push_back(u);
						g[u][i].push_back(j);
						if (max(g[j][i].size(), g[u][i].size()) > 2 || !merge(i, j, u)) bad[i] = true;
					}
				}
			}
		}
		if (!merge(0, A, B)){
			if (cycle != 0) bad[0] = true;
			cycle = -par[0][getpar(0, A)];
		}
		return;
	}
	for (int i = 1; i <= ver.size(); i++){
		if (A != ver[i-1] && B != ver[i-1]){
			g[A][i].push_back(B);
			g[B][i].push_back(A);
			if (max(g[A][i].size(), g[B][i].size()) > 2 || !merge(i, A, B)) bad[i] = true;
		}
	}
}

int CountCritical() {
	if (!bad[0]){
		if (cycle == 0) return n;
		return cycle;
	}
	int ans = 0;
	for (int i = 1; i <= ver.size(); i++){
		ans += (!bad[i]);
	}
	return ans;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 1; i <= ver.size(); i++){
      |                    ~~^~~~~~~~~~~~~
rings.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for (int i = 1; i <= ver.size(); i++){
      |                    ~~^~~~~~~~~~~~~
rings.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 1; i <= ver.size(); i++){
      |                  ~~^~~~~~~~~~~~~
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 = 1; i <= ver.size(); i++){
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 0 / 31