oj.uz

Submission #955155

# Submission time Handle Problem Language Result Execution time Memory
955155 2024-03-29T13:36:40 Z djs100201 Werewolf (IOI18_werewolf) C++17
Compilation error
 0 ms 0 KB 
#include<bits/stdc++.h>
#include<werewolf.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =4e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 1e9+7;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
//ctrl + g ->줄이동
 
class seg{
	public:
	vector<ll>tree;
	ll base;
	seg(int n){
		for(base=1;base<=n;base*=2);
		//0~n쓰겠다
		tree.resize(n*4+4,-inf);
	}
	ll f(ll l,ll r){
		l+=base,r+=base;
		ll ret=-inf;
		while(l<=r){
			if(l%2)ret=max(ret,tree[l++]);
			if(!(r%2))ret=max(ret,tree[r--]);
			l/=2,r/=2;
		}
		return ret;
	}
	void update(ll i,ll v){
		i+=base;
		tree[i]=max(tree[i],v);
		i/=2;
		while(i){
			tree[i]=max(tree[i*2],tree[i*2+1]);
			i/=2;
		}
	}
};
class UF{
	public:
	vector<int>par;
	UF(int n){
		par.resize(n+1);
		for(int i=0;i<=n;i++)par[i]=-1;
	}
	int find(int x){
		if(par[x]==-1)return x;
		return par[x]=find(par[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		par[x]=y;
	}
};
class graph{
	public:
	vector<vector<ll>>edge;
	vector<ll>in,out;
	int cnt;
	graph(int n){
		edge.resize(n+1);
		in.resize(n+1);
		out.resize(n+1);
		cnt=0;
	}
	void add_edge(int u,int v){
		u=find(u),v=find(v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	void dfs(ll x,ll par){
		in[x]=cnt++;
		for(auto nxt:edge[x]){
			if(nxt==par)continue;
			dfs(nxt,x);
		}
		out[x]=cnt-1;
	}
};
vector<ll>v1[n_],v2[n_],LQ[n_],RQ[n_],XX[n_],XQ[n_];
ll Lidx[n_],Ridx[n_];
vector<P>YQ[n_];
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
	n=N;
	ll q=L.size();
	vector<int>ret(q);
	for(int i=0;i<q;i++){
		LQ[L[i]].push_back(i);
		RQ[R[i]].push_back(i);
	}
	for(int i=0;i<X.size();i++){
		if(X[i]>Y[i])swap(X[i],Y[i]);
		v1[X[i]].push_back(Y[i]);
		v2[Y[i]].push_back(X[i]);
	}
	
	UF LL(2*n),RR(2*n);
	graph LG(2*n),RG(2*n);
 
	base=n;
	for(int i=n-1;i>=0;i--){
		for(auto nxt:v1[i]){
			if(LL.find(i)==LL.find(nxt))continue;
			LG.add_edge(i,base),LG.add_edge(nxt,base);
			LL.merge(i,base),LL.merge(nxt,base);
			base++;
		}
		for(auto nxt:LQ[i])Lidx[nxt]=LL.find(S[nxt]);
	}
	LG.dfs(base-1,-1);
	base=n;
	for(int i=0;i<n;i++){
		for(auto nxt:v2[i]){
			if(RR.find(i)==RR.find(nxt))continue;
			RG.add_edge(i,base),RG.add_edge(nxt,base);
			RR.merge(i,base),RR.merge(nxt,base);
			base++;
		}
		for(auto nxt:RQ[i])Ridx[nxt]=RR.find(E[nxt]);
	}
	RG.dfs(base-1,-1);
	for(int i=0;i<n;i++)XX[LG.in[i]].push_back(RG.in[i]);
	for(int i=0;i<q;i++)XQ[LG.out[Lidx[i]]].push_back(i);
	seg seg_(n*2+100);
	for(int i=0;i<n_;i++){
		for(auto nxt:XX[i])seg_.update(nxt,i);
		for(auto nxt:XQ[i]){
			if(LG.in[Lidx[nxt]]<=seg_.f(RG.in[Ridx[nxt]],RG.out[Ridx[nxt]]))ret[nxt]=1;
			else ret[nxt]=0;
		}
	}
	return ret;
}

Compilation message

werewolf.cpp: In member function 'void graph::add_edge(int, int)':
werewolf.cpp:78:11: error: no matching function for call to 'find(int&)'
   78 |   u=find(u),v=find(v);
      |           ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
werewolf.cpp:78:11: note:   mismatched types 'std::istreambuf_iterator<_CharT>' and 'int'
   78 |   u=find(u),v=find(v);
      |           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: candidate: 'template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)'
 3894 |     find(_InputIterator __first, _InputIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:3894:5: note:   template argument deduction/substitution failed:
werewolf.cpp:78:11: note:   candidate expects 3 arguments, 1 provided
   78 |   u=find(u),v=find(v);
      |           ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from werewolf.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:60:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::find(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
   60 | find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:60:1: note:   template argument deduction/substitution failed:
werewolf.cpp:78:11: note:   candidate expects 4 arguments, 1 provided
   78 |   u=find(u),v=find(v);
      |           ^
werewolf.cpp:78:21: error: no matching function for call to 'find(int&)'
   78 |   u=find(u),v=find(v);
      |                     ^
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
  422 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note:   template argument deduction/substitution failed:
werewolf.cpp:78:21: note:   mismatched types 'std::istreambuf_iterator<_CharT>' and 'int'
   78 |   u=find(u),v=find(v);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: candidate: 'template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)'
 3894 |     find(_InputIterator __first, _InputIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:3894:5: note:   template argument deduction/substitution failed:
werewolf.cpp:78:21: note:   candidate expects 3 arguments, 1 provided
   78 |   u=find(u),v=find(v);
      |                     ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from werewolf.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:60:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::find(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
   60 | find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:60:1: note:   template argument deduction/substitution failed:
werewolf.cpp:78:21: note:   candidate expects 4 arguments, 1 provided
   78 |   u=find(u),v=find(v);
      |                     ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i=0;i<X.size();i++){
      |              ~^~~~~~~~~