oj.uz

Submission #379333

# Submission time Handle Problem Language Result Execution time Memory
379333 2021-03-18T02:20:01 Z autumn_eel Werewolf (IOI18_werewolf) C++14
Compilation error
 0 ms 0 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

const int INF=0x3f3f3f3f;

struct UnionFind{
	vector<int>par;
	UnionFind(int n){
		par=vector<int>(n);
		rep(i,n)par[i]=i;
	}
	int find(int x){
		return par[x]==x?x:par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		par[y]=x;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
};

struct Segtree{
	int N;
	vector<int>dat;
	function<int(int,int)>f;
	int ini;

	Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,ini);
	}

	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=f(dat[k*2],dat[k*2+1]);
		}
	}

	int query(int l,int r){
		int res=ini;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=f(res,dat[l++]);
			if(r&1)res=f(res,dat[--r]);
		}
		return res;
	}

};
vector<int>E[300000];
int pos[300000];

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	if(N<=3000&&M<=6000&&Q<=3000){
		int M=X.size();
		int Q=S.size();
		vector<int>ans;
		rep(i,Q){
			UnionFind uf1(N),uf2(N);
			rep(j,M){
				if(X[j]>=L[i]&&Y[j]>=L[i])uf1.unite(X[j],Y[j]);
				if(X[j]<=R[i]&&Y[j]<=R[i])uf2.unite(X[j],Y[j]);
			}
			bool ok=false;
			rep(j,N){
				if(uf1.same(S[i],j)&&uf2.same(E[i],j)){
					ok=true;break;
				}
			}
			ans.push_back(ok);
		}
		return ans;
	}
	rep(i,M){
		E[X[i]].push_back(Y[i]);
		E[Y[i]].push_back(X[i]);
	}
	int s=-1;
	rep(i,N){
		if(E[i].size()==1){
			s=i;break;
		}
	}
	vector<int>vs;
	memset(pos,-1,sizeof(pos));
	rep(i,N){
		vs.push_back(s);
		pos[s]=i;
		for(int u:E[s]){
			if(pos[u]==-1){
				s=u;
			}
		}
	}
	Segtree seg1(N,INF,[](int a,int b){return min(a,b);});
	Segtree seg2(N,0,[](int a,int b){return max(a,b);});
	rep(i,N){
		seg1.update(i,vs[i]);
		seg2.update(i,vs[i]);
	}
	vector<int>ans;
	rep(i,Q){
		int s=pos[S[i]],e=pos[E[i]];
		if(s<e){
			int ok1=s,ng1=N;
			while(ng1-ok1>1){
				int t=(ok1+ng1)/2;
				if(seg1.query(s,t+1)>=L[i])ok1=t;
				else ng1=t;
			}
			int ok2=e,ng2=-1;
			while(ok2-ng2>1){
				int t=(ok2+ng2)/2;
				if(seg2.query(t,e+1)<=R[i])ok2=t;
				else ng2=t;
			}
			ans.push_back(ok2<=ok1);
		}
		else{
			int ok1=s,ng1=-1;
			while(ok1-ng1>1){
				int t=(ok1+ng1)/2;
				if(seg1.query(t,s+1)>=L[i])ok1=t;
				else ng1=t;
			}
			int ok2=e,ng2=N;
			while(ng2-ok2>1){
				int t=(ok2+ng2)/2;
				if(seg2.query(e,t+1)<=R[i])ok2=t;
				else ng2=t;
			}
			ans.push_back(ok1<=ok2);
		}
	}
	return ans;
}

Compilation message

werewolf.cpp:32:45: error: expression list treated as compound expression in functional cast [-fpermissive]
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                             ^
werewolf.cpp:32:46: error: template argument 1 is invalid
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                              ^
werewolf.cpp:32:45: error: expression list treated as compound expression in functional cast [-fpermissive]
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                             ^
werewolf.cpp:32:46: error: template argument 1 is invalid
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                              ^
werewolf.cpp:32:45: error: expression list treated as compound expression in functional cast [-fpermissive]
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                             ^
werewolf.cpp:32:46: error: template argument 1 is invalid
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                              ^
werewolf.cpp:32:24: error: 'function' is not a type
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                        ^~~~~~~~
werewolf.cpp:32:32: error: expected ',' or '...' before '<' token
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                                ^
werewolf.cpp: In constructor 'Segtree::Segtree(int, int, int)':
werewolf.cpp:30:6: warning: 'Segtree::ini' will be initialized after [-Wreorder]
   30 |  int ini;
      |      ^~~
werewolf.cpp:29:24: warning:   'std::function<int(int, int)> Segtree::f' [-Wreorder]
   29 |  function<int(int,int)>f;
      |                        ^
werewolf.cpp:32:2: warning:   when initialized here [-Wreorder]
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |  ^~~~~~~
werewolf.cpp:32:2: warning: 'Segtree::f' is initialized with itself [-Winit-self]
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:61:14: error: 'M' was not declared in this scope
   61 |  if(N<=3000&&M<=6000&&Q<=3000){
      |              ^
werewolf.cpp:61:23: error: 'Q' was not declared in this scope
   61 |  if(N<=3000&&M<=6000&&Q<=3000){
      |                       ^
werewolf.cpp:62:7: error: redeclaration of 'int M'
   62 |   int M=X.size();
      |       ^
werewolf.cpp:61:14: note: '<typeprefixerror>M' previously declared here
   61 |  if(N<=3000&&M<=6000&&Q<=3000){
      |              ^
werewolf.cpp:63:7: error: redeclaration of 'int Q'
   63 |   int Q=S.size();
      |       ^
werewolf.cpp:61:23: note: '<typeprefixerror>Q' previously declared here
   61 |  if(N<=3000&&M<=6000&&Q<=3000){
      |                       ^
werewolf.cpp:81:8: error: 'M' was not declared in this scope
   81 |  rep(i,M){
      |        ^
werewolf.cpp:3:32: note: in definition of macro 'rep'
    3 | #define rep(i,n)for(int i=0;i<(n);i++)
      |                                ^
werewolf.cpp:82:11: error: request for member 'push_back' in 'E.std::vector<int>::operator[](((std::vector<int>::size_type)X.std::vector<int>::operator[](((std::vector<int>::size_type)i))))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   82 |   E[X[i]].push_back(Y[i]);
      |           ^~~~~~~~~
werewolf.cpp:83:11: error: request for member 'push_back' in 'E.std::vector<int>::operator[](((std::vector<int>::size_type)Y.std::vector<int>::operator[](((std::vector<int>::size_type)i))))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   83 |   E[Y[i]].push_back(X[i]);
      |           ^~~~~~~~~
werewolf.cpp:87:11: error: request for member 'size' in 'E.std::vector<int>::operator[](((std::vector<int>::size_type)i))', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   87 |   if(E[i].size()==1){
      |           ^~~~
werewolf.cpp:96:16: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   96 |   for(int u:E[s]){
      |                ^
      |                std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from werewolf.cpp:2:
/usr/include/c++/9/valarray:1224:5: note: 'std::begin' declared here
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
werewolf.cpp:96:16: error: 'end' was not declared in this scope; did you mean 'std::end'?
   96 |   for(int u:E[s]){
      |                ^
      |                std::end
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from werewolf.cpp:2:
/usr/include/c++/9/valarray:1244:5: note: 'std::end' declared here
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
werewolf.cpp:102:54: error: invalid user-defined conversion from 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, int)>' to 'int' [-fpermissive]
  102 |  Segtree seg1(N,INF,[](int a,int b){return min(a,b);});
      |                                                      ^
werewolf.cpp:102:21: note: candidate is: 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, int)>::operator int (*)(int, int)() const' <near match>
  102 |  Segtree seg1(N,INF,[](int a,int b){return min(a,b);});
      |                     ^
werewolf.cpp:102:21: note:   no known conversion from 'int (*)(int, int)' to 'int'
werewolf.cpp:32:24: note:   initializing argument 3 of 'Segtree::Segtree(int, int, int)'
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                        ^~~~~~~~
werewolf.cpp:103:52: error: invalid user-defined conversion from 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, int)>' to 'int' [-fpermissive]
  103 |  Segtree seg2(N,0,[](int a,int b){return max(a,b);});
      |                                                    ^
werewolf.cpp:103:19: note: candidate is: 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(int, int)>::operator int (*)(int, int)() const' <near match>
  103 |  Segtree seg2(N,0,[](int a,int b){return max(a,b);});
      |                   ^
werewolf.cpp:103:19: note:   no known conversion from 'int (*)(int, int)' to 'int'
werewolf.cpp:32:24: note:   initializing argument 3 of 'Segtree::Segtree(int, int, int)'
   32 |  Segtree(int n,int ini,function<int(int,int>)f):ini(ini),f(f){
      |                        ^~~~~~~~
werewolf.cpp:109:8: error: 'Q' was not declared in this scope
  109 |  rep(i,Q){
      |        ^
werewolf.cpp:3:32: note: in definition of macro 'rep'
    3 | #define rep(i,n)for(int i=0;i<(n);i++)
      |                                ^