Submission #97780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97780	2019-02-18T13:04:45 Z	E869120	Parachute rings (IOI12_rings)	C++14	Compilation error	0 ms	0 KB

rings

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
	public:
	vector<int>G, H; vector<int> group[1000009]; int CurrentSum, size_;
	vector<bool>I;
	
	void init(int sz){
		G.resize(sz, 0);
		H.resize(sz, 0);
		I.resize(sz, false);
		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:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int t = 0; t < s3.size(); t++) {
                   ~~^~~~~~~~~~~
rings.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v1.size(); i++) {
                   ~~^~~~~~~~~~~
rings.cpp:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < v2.size(); j++) {
                    ~~^~~~~~~~~~~
rings.cpp:85: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:100: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:100: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:101: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:101: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);
                                  ^~
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status