Submission #24148

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24148	2017-05-31T13:47:28 Z	Hiasat	Parachute rings (IOI12_rings)	C++14	Compilation error	0 ms	0 KB

rings

#include <bits/stdc++.h>

using namespace std;
const int MX = 1000001;

const int CHAIN = 0;
const int CYCLE = 1;
const int THREE = 2;
const int BIG = 3;
const int BLOCKED = 4;

int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
vector<int> adj[1000001];
bool block[1000001];

int res = 0,ff2[10];
bool ZERO = 0;

int find(int u) {
	return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}
void Init(int N_) {
	N = N_;
	for (int i = 0; i < N; ++i) {
		dsu[i] = i;
		freq[i][0] = 1;
		prev[i] = 1;
		res += prev[i];
		E[i] = 0;
		sz[i] = 1;
		ff2[0]++;
	}
}
bool fn(int u, int p) {
	if (vis[u] == vsId) {
		return false;
	}
	if (!block[u] && in[u] > 2)
		return false;
	vis[u] = vsId;
	for (int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i];
		if (v == p || block[v])
			continue;
		if (block[u] && vis[v] == vsId)
			continue;
		if (!fn(v, u))
			return false;
	}
	return true;
}

bool check(int u , int p) {
	block[u] = 1;
	vsId++;
	for (int i = 0; i < adj[u].size(); ++i) {
		in[adj[u][i]]--;
	}
	bool res = fn(u, p);
	for (int i = 0; i < adj[u].size(); ++i) {
		in[adj[u][i]]++;
	}
	block[u] = 0;
	return res;
}

void Link(int A, int B) {
	if (ZERO)
		return;
	adj[A].push_back(B);
	adj[B].push_back(A);
	if (type[find(A)] == BLOCKED || type[find(B)] == BLOCKED)
		return;
	if (find(A) == find(B) && (B == big[find(A)][4] || A == big[find(B)][4]))
		return;
	freq[find(A)][in[A]]--;
	freq[find(B)][in[B]]--;
	in[A]++, in[B]++;
	in[A] = min(in[A], 4);
	in[B] = min(in[B], 4);
	freq[find(A)][in[A]]++;
	freq[find(B)][in[B]]++;
	res -= prev[find(A)];
	ff2[type[find(A)]]--;
	if (find(A) != find(B)) {
		ff2[type[find(B)]]--;
		res -= prev[find(B)];
		for (int i = 0 ; i <= 4  ; i++) {
			if (in[A] == i) {
				big[find(A)][i] = A;
			}
			if (in[B] == i) {
				big[find(B)][i] = B;
			}
		}
		E[find(B)] += E[find(A)];
		sz[find(B)] += sz[find(A)];
		for (int i = 0; i <= 4; ++i) {
			big[find(B)][i] = max(big[find(B)][i], big[find(A)][i]);
			freq[find(B)][i] += freq[find(A)][i];
		}
		dsu[find(A)] = find(B);
	}
	E[find(B)]++;
	if (freq[find(A)][4] > 1 || freq[find(A)][3] > 4) {
		type[find(A)] = BLOCKED;
		ZERO = 1;
	} else if (freq[find(A)][4]) {
		type[find(A)] = BIG;
		prev[find(A)] = 0;
		if (check(big[find(A)][4], -1)) {
			prev[find(A)]++;
		}
		res += prev[find(A)];
	} else if (freq[find(A)][3]) {
		type[find(A)]= THREE;
		prev[find(A)] = 0;
		if(check(big[find(A)][3],-1))
			prev[find(A)]++;
		for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) {
			int v = adj[big[find(A)][3]][j];
			if (check(v, -1)) {
				prev[find(A)]++;
			}
		}
		res += prev[find(A)];
	} else {
		if (freq[find(A)][2] == sz[find(A)]) {
			type[find(A)] = CYCLE;
		}
		prev[find(A)] = sz[find(A)];
		res += prev[find(A)];
	}
	ff2[type[find(A)]]++;
	last[type[find(A)]] = find(A);
}

int CountCritical() {
	if (ZERO)
		return 0;
	int fn = 0;
	for (int i = 1; i <= 3; ++i){
		fn += type[i];
	}
	if(fn > 1)
		return 0;
	for (int i = 1; i <= 3; ++i){
		if(ff2[i]){
			return prev[last[i]];
		}
	}
	return res;
}

Compilation message

rings.cpp: In function 'void Init(int)':
rings.cpp:27:3: error: reference to 'prev' is ambiguous
   prev[i] = 1;
   ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:28:10: error: reference to 'prev' is ambiguous
   res += prev[i];
          ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp: In function 'bool fn(int, int)':
rings.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'bool check(int, int)':
rings.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:83:9: error: reference to 'prev' is ambiguous
  res -= prev[find(A)];
         ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:87:10: error: reference to 'prev' is ambiguous
   res -= prev[find(B)];
          ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:110:3: error: reference to 'prev' is ambiguous
   prev[find(A)] = 0;
   ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:112:4: error: reference to 'prev' is ambiguous
    prev[find(A)]++;
    ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:114:10: error: reference to 'prev' is ambiguous
   res += prev[find(A)];
          ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:117:3: error: reference to 'prev' is ambiguous
   prev[find(A)] = 0;
   ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:119:4: error: reference to 'prev' is ambiguous
    prev[find(A)]++;
    ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0 ; j < adj[big[find(A)][3]].size(); j++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rings.cpp:123:5: error: reference to 'prev' is ambiguous
     prev[find(A)]++;
     ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:126:10: error: reference to 'prev' is ambiguous
   res += prev[find(A)];
          ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:131:3: error: reference to 'prev' is ambiguous
   prev[find(A)] = sz[find(A)];
   ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp:132:10: error: reference to 'prev' is ambiguous
   res += prev[find(A)];
          ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:149:11: error: reference to 'prev' is ambiguous
    return prev[last[i]];
           ^~~~
rings.cpp:12:130: note: candidates are: int prev [1000001]
 int dsu[1000001],last[10], E[1000001], freq[1000001][5], sz[1000001], in[1000001], big[1000001][5], vis[1000001], type[1000001], prev[1000001], vsId, N;
                                                                                                                                  ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from rings.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:220:5: note:                 template<class _BidirectionalIterator> _BidirectionalIterator std::prev(_BidirectionalIterator, typename std::iterator_traits<_Iter>::difference_type)
     prev(_BidirectionalIterator __x, typename
     ^~~~