oj.uz

Submission #97778

# Submission time Handle Problem Language Result Execution time Memory
97778 2019-02-18T13:01:13 Z E869120 Parachute rings (IOI12_rings) C++14
20 / 100
 1428 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 (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])));
		}
	}
	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:74: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:89: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:89: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:90: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:90: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 40 ms 25600 KB Output is correct
3 Correct 31 ms 25728 KB Output is correct
4 Correct 30 ms 24064 KB Output is correct
5 Correct 29 ms 24312 KB Output is correct
6 Correct 34 ms 24576 KB Output is correct
7 Correct 37 ms 26752 KB Output is correct
8 Correct 31 ms 24312 KB Output is correct
9 Correct 42 ms 26872 KB Output is correct
10 Correct 37 ms 27016 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 82112 KB Output is correct
2 Runtime error 1428 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 40 ms 25600 KB Output is correct
3 Correct 31 ms 25728 KB Output is correct
4 Correct 30 ms 24064 KB Output is correct
5 Correct 29 ms 24312 KB Output is correct
6 Correct 34 ms 24576 KB Output is correct
7 Correct 37 ms 26752 KB Output is correct
8 Correct 31 ms 24312 KB Output is correct
9 Correct 42 ms 26872 KB Output is correct
10 Correct 37 ms 27016 KB Output is correct
11 Incorrect 36 ms 25804 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 40 ms 25600 KB Output is correct
3 Correct 31 ms 25728 KB Output is correct
4 Correct 30 ms 24064 KB Output is correct
5 Correct 29 ms 24312 KB Output is correct
6 Correct 34 ms 24576 KB Output is correct
7 Correct 37 ms 26752 KB Output is correct
8 Correct 31 ms 24312 KB Output is correct
9 Correct 42 ms 26872 KB Output is correct
10 Correct 37 ms 27016 KB Output is correct
11 Incorrect 36 ms 25804 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 40 ms 25600 KB Output is correct
3 Correct 31 ms 25728 KB Output is correct
4 Correct 30 ms 24064 KB Output is correct
5 Correct 29 ms 24312 KB Output is correct
6 Correct 34 ms 24576 KB Output is correct
7 Correct 37 ms 26752 KB Output is correct
8 Correct 31 ms 24312 KB Output is correct
9 Correct 42 ms 26872 KB Output is correct
10 Correct 37 ms 27016 KB Output is correct
11 Correct 1077 ms 82112 KB Output is correct
12 Runtime error 1428 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -