oj.uz

Submission #97779

# Submission time Handle Problem Language Result Execution time Memory
97779 2019-02-18T13:03:33 Z E869120 Parachute rings (IOI12_rings) C++14
20 / 100
 1453 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
	public:
	vector<int>G, H; vector<vector<int>> group; int CurrentSum, size_;
	vector<bool>I;
	
	void init(int sz){
		G.resize(sz, 0);
		H.resize(sz, 0);
		I.resize(sz, false);
		group.resize(sz);
		for (int i = 0; i < sz; i++) G[i] = i;
		for (int i = 0; i < sz; i++) group[i].push_back(i);
		CurrentSum = sz; size_ = sz;
	}
	void unite(int u, int v) {
		H[u]++; H[v]++;
		if (H[u] >= 3) { CurrentSum = 0; I[G[u]] = true; return; }
		if (H[v] >= 3) { CurrentSum = 0; I[G[v]] = true; return; }
		u = G[u]; v = G[v];
		if (group[u].size() < group[v].size()) swap(u, v);
		
		if (u == v) {
			if (I[u] == false) { I[u] = true; if (CurrentSum == size_) CurrentSum = (int)group[u].size(); else CurrentSum = 0; }
			return;
		}
		
		for (int i = 0; i < (int)group[v].size(); i++) {
			group[u].push_back(group[v][i]);
			G[group[v][i]] = u;
		}
		group[v].clear();
	}
};

int N, Q, cnts, M[1000009]; bool ok = false;
vector<pair<int, int>> G; vector<int> X[1000009]; 

// For rankers
int K[109]; UnionFind XX[109]; int KKK[1000009];
vector<pair<int, int>> rankers; vector<int>s3, s4; bool used[109];

int refs(int pos) {
	if (KKK[pos] >= 1) return KKK[pos];
	
	int V = 0; for (int i = 1; i < 19; i++) { if (used[i] == false) { V = i; break; } }
	KKK[pos] = V; XX[V].init(N); K[V] = pos;
	for (int i = 0; i < (int)G.size(); i++) {
		int u = G[i].first, v = G[i].second; if (pos == u || pos == v) continue;
		XX[V].unite(u, v);
	}
	used[V] = true;
	return V;
}

void refresh() {
	if ((int)s4.size() >= 2) { rankers.clear(); return; }
	if ((int)s3.size() >= 3) { rankers.clear(); return; }
	
	rankers.clear();
	for (int i = 0; i < (int)s3.size(); i++) rankers.push_back(make_pair(s3[i], refs(s3[i])));
	if (s3.size() == 1 && s4.size() == 0) {
		for (int t = 0; t < s3.size(); t++) {
			int pos1 = s3[t];
			for (int i = 0; i < (int)X[pos1].size(); i++) {
				rankers.push_back(make_pair(X[pos1][i], refs(X[pos1][i])));
			}
		}
	}
	if (s3.size() == 2 && s4.size() == 0) {
		vector<int> v1 = X[s3[0]];
		vector<int> v2 = X[s3[1]];
		for (int i = 0; i < v1.size(); i++) {
			for (int j = 0; j < v2.size(); j++) {
				int pos1 = v1[i];
				if (v1[i] == v2[j]) rankers.push_back(make_pair(pos1, refs(pos1)));
			}
		}
	}
	sort(rankers.begin(), rankers.end());
	rankers.erase(unique(rankers.begin(), rankers.end()), rankers.end());
	
	for (int i = 1; i < 19; i++) used[i] = false;
	for (int i = 0; i < rankers.size(); i++) used[rankers[i].second] = true;
	if (rankers.size() >= 1) ok = true;
}

void Link_(int u, int v) {
	G.push_back(make_pair(u, v));
	X[u].push_back(v);
	X[v].push_back(u);
	for (int i = 0; i < (int)rankers.size(); i++) {
		int pos = rankers[i].second;
		if (K[pos] == u || K[pos] == v) continue;
		XX[pos].unite(u, v); 
	}
	XX[0].unite(u, v);
	M[u]++; M[v]++;
	if (M[u] == 3) s3.push_back(u); if (M[u] == 4) s4.push_back(u);
	if (M[v] == 3) s3.push_back(v); if (M[v] == 4) s4.push_back(v);
	
	refresh();
	//cout << "#"; for (int i = 0; i < (int)rankers.size(); i++) cout << rankers[i].second << " "; cout << endl;
}

void Init(int N_) {
	N = N_; XX[0].init(N);
}

void Link(int A, int B) {
	Link_(A, B);
}

int CountCritical() {
	int ret = 0;
	if (ok == false) ret = XX[0].CurrentSum;
	else {
		for (int i = 0; i < (int)rankers.size(); i++) {
			int pos = rankers[i].second; 
			if (XX[pos].CurrentSum == N) ret++;
		}
	}
	return ret;
}

Compilation message

rings.cpp: In function 'void refresh()':
rings.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int t = 0; t < s3.size(); t++) {
                   ~~^~~~~~~~~~~
rings.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v1.size(); i++) {
                   ~~^~~~~~~~~~~
rings.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < v2.size(); j++) {
                    ~~^~~~~~~~~~~
rings.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rankers.size(); i++) used[rankers[i].second] = true;
                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link_(int, int)':
rings.cpp:101:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (M[u] == 3) s3.push_back(u); if (M[u] == 4) s4.push_back(u);
  ^~
rings.cpp:101:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (M[u] == 3) s3.push_back(u); if (M[u] == 4) s4.push_back(u);
                                  ^~
rings.cpp:102:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (M[v] == 3) s3.push_back(v); if (M[v] == 4) s4.push_back(v);
  ^~
rings.cpp:102:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (M[v] == 3) s3.push_back(v); if (M[v] == 4) s4.push_back(v);
                                  ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 33 ms 25472 KB Output is correct
3 Correct 37 ms 25896 KB Output is correct
4 Correct 26 ms 23936 KB Output is correct
5 Correct 27 ms 24260 KB Output is correct
6 Correct 30 ms 24572 KB Output is correct
7 Correct 28 ms 25820 KB Output is correct
8 Correct 33 ms 24312 KB Output is correct
9 Correct 40 ms 25876 KB Output is correct
10 Correct 45 ms 26232 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1084 ms 81952 KB Output is correct
2 Runtime error 1453 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 33 ms 25472 KB Output is correct
3 Correct 37 ms 25896 KB Output is correct
4 Correct 26 ms 23936 KB Output is correct
5 Correct 27 ms 24260 KB Output is correct
6 Correct 30 ms 24572 KB Output is correct
7 Correct 28 ms 25820 KB Output is correct
8 Correct 33 ms 24312 KB Output is correct
9 Correct 40 ms 25876 KB Output is correct
10 Correct 45 ms 26232 KB Output is correct
11 Incorrect 34 ms 25848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 33 ms 25472 KB Output is correct
3 Correct 37 ms 25896 KB Output is correct
4 Correct 26 ms 23936 KB Output is correct
5 Correct 27 ms 24260 KB Output is correct
6 Correct 30 ms 24572 KB Output is correct
7 Correct 28 ms 25820 KB Output is correct
8 Correct 33 ms 24312 KB Output is correct
9 Correct 40 ms 25876 KB Output is correct
10 Correct 45 ms 26232 KB Output is correct
11 Incorrect 34 ms 25848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 33 ms 25472 KB Output is correct
3 Correct 37 ms 25896 KB Output is correct
4 Correct 26 ms 23936 KB Output is correct
5 Correct 27 ms 24260 KB Output is correct
6 Correct 30 ms 24572 KB Output is correct
7 Correct 28 ms 25820 KB Output is correct
8 Correct 33 ms 24312 KB Output is correct
9 Correct 40 ms 25876 KB Output is correct
10 Correct 45 ms 26232 KB Output is correct
11 Correct 1084 ms 81952 KB Output is correct
12 Runtime error 1453 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -