oj.uz

답안 #97778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97778 2019-02-18T13:01:13 Z E869120 낙하산 고리들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -