oj.uz

답안 #97777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97777 2019-02-18T13:00:19 Z E869120 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 3639 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]; map<pair<int, int>,int> Map;
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)); Map[make_pair(u, v)] = 1; Map[make_pair(v, u)] = 1;
	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 28 ms 23936 KB Output is correct
2 Correct 41 ms 25976 KB Output is correct
3 Correct 44 ms 26616 KB Output is correct
4 Correct 35 ms 24084 KB Output is correct
5 Correct 33 ms 24696 KB Output is correct
6 Correct 34 ms 25208 KB Output is correct
7 Correct 34 ms 26868 KB Output is correct
8 Correct 32 ms 24828 KB Output is correct
9 Correct 51 ms 27640 KB Output is correct
10 Correct 53 ms 27640 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3639 ms 153824 KB Output is correct
2 Runtime error 2228 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 28 ms 23936 KB Output is correct
2 Correct 41 ms 25976 KB Output is correct
3 Correct 44 ms 26616 KB Output is correct
4 Correct 35 ms 24084 KB Output is correct
5 Correct 33 ms 24696 KB Output is correct
6 Correct 34 ms 25208 KB Output is correct
7 Correct 34 ms 26868 KB Output is correct
8 Correct 32 ms 24828 KB Output is correct
9 Correct 51 ms 27640 KB Output is correct
10 Correct 53 ms 27640 KB Output is correct
11 Incorrect 43 ms 26600 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 23936 KB Output is correct
2 Correct 41 ms 25976 KB Output is correct
3 Correct 44 ms 26616 KB Output is correct
4 Correct 35 ms 24084 KB Output is correct
5 Correct 33 ms 24696 KB Output is correct
6 Correct 34 ms 25208 KB Output is correct
7 Correct 34 ms 26868 KB Output is correct
8 Correct 32 ms 24828 KB Output is correct
9 Correct 51 ms 27640 KB Output is correct
10 Correct 53 ms 27640 KB Output is correct
11 Incorrect 43 ms 26600 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 23936 KB Output is correct
2 Correct 41 ms 25976 KB Output is correct
3 Correct 44 ms 26616 KB Output is correct
4 Correct 35 ms 24084 KB Output is correct
5 Correct 33 ms 24696 KB Output is correct
6 Correct 34 ms 25208 KB Output is correct
7 Correct 34 ms 26868 KB Output is correct
8 Correct 32 ms 24828 KB Output is correct
9 Correct 51 ms 27640 KB Output is correct
10 Correct 53 ms 27640 KB Output is correct
11 Correct 3639 ms 153824 KB Output is correct
12 Runtime error 2228 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -