답안 #899900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899900	2024-01-07T09:14:06 Z	PM1	Mergers (JOI19_mergers)	C++17	컴파일 오류	0 ms	0 KB

mergers

#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+5;
int n,par[mxn][22],num[mxn],k,s[mxn],st[mxn],fn[mxn],cnt=0,sz[mxn],comp[mxn],ans=0,count[mxn];
bool marky[mxn];
struct yall{
	int u,uu;
}yal[mxn];
vector<int>v[mxn],act[mxn];
void pre(int z){
	st[z]=++cnt;
	act[s[z]].push_back(z);
	for(int i=1;i<=21;i++)
		par[z][i]=par[par[z][i-1]][i-1];
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(par[z][0]!=x){
			par[x][0]=z;
			pre(x);
		}
	}
	if(act[s[z]].back()==z)num[z]--,count[s[z]]++;
	fn[z]=cnt;
}
int lca(int x,int y){
	if(st[x]<=st[y] && fn[x]>=fn[y])return x;
	for(int i=21;i>=0;i--){
		if(par[x][i]==0)continue;
		if(st[par[x][i]]>st[y] || fn[par[x][i]]<st[y])x=par[x][i];
	}
	return par[x][0];
}
void dfs(int z,int y=0,int sum=0){
	if(sum==0)
		marky[y]=1;
	sum+=num[z];
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(x!=par[z][0]){
			dfs(x,i,sum);
			
		}
	}
	sum-=num[z];
}
void fds(int z){
	comp[z]=cnt;
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(!comp[x] && !marky[i])
			fds(x);
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		cin>>yal[i].u>>yal[i].uu;
		v[yal[i].u].push_back(i);
		v[yal[i].uu].push_back(i);
	}
	for(int i=1;i<=n;i++)
		cin>>s[i];
	pre(1);
	for(int i=1;i<=k;i++){
			int x=act[i][0];
			for(int j=1;j<act[i].size();j++){
				x=lca(x,act[i][j]);
			}
			num[x]+=count[i];
	}
	dfs(1);
	cnt=1;
	for(int i=1;i<=n;i++){
		if(!comp[i]){
			fds(i);
			cnt++;
		}
	}
	for(int i=1;i<n;i++){
		if(marky[i]){
			sz[comp[yal[i].u]]++;
			sz[comp[yal[i].uu]]++;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(sz[i]==1)ans++;
	}
	if(ans==1 || cnt<=2)
		cout<<0<<'\n';
	else
		cout<<(ans+1)/2<<endl;
}

Compilation message

mergers.cpp: In function 'void pre(int)':
mergers.cpp:22:34: error: reference to 'count' is ambiguous
   22 |  if(act[s[z]].back()==z)num[z]--,count[s[z]]++;
      |                                  ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
mergers.cpp:4:84: note:                 'int count [500005]'
    4 | int n,par[mxn][22],num[mxn],k,s[mxn],st[mxn],fn[mxn],cnt=0,sz[mxn],comp[mxn],ans=0,count[mxn];
      |                                                                                    ^~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int j=1;j<act[i].size();j++){
      |                ~^~~~~~~~~~~~~~
mergers.cpp:69:12: error: reference to 'count' is ambiguous
   69 |    num[x]+=count[i];
      |            ^~~~~
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:101:1: note: candidates are: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, typename std::iterator_traits<_II>::difference_type> std::count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
  101 | count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~~
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4077:5: note:                 'template<class _IIter, class _Tp> typename std::iterator_traits< <template-parameter-1-1> >::difference_type std::count(_IIter, _IIter, const _Tp&)'
 4077 |     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
      |     ^~~~~
mergers.cpp:4:84: note:                 'int count [500005]'
    4 | int n,par[mxn][22],num[mxn],k,s[mxn],st[mxn],fn[mxn],cnt=0,sz[mxn],comp[mxn],ans=0,count[mxn];
      |                                                                                    ^~~~~