Submission #899875

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
899875	2024-01-07T08:10:05 Z	PM1	Mergers (JOI19_mergers)	C++17	Compilation error	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;
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);
		}
	}
	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[i]=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-=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];
			num[x]--;
			for(int j=1;j<act[i].size();j++){
				num[act[i][j]]--;
				x=lca(x,act[i][j]);
			}
			num[x]++;
	}
	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 dfs(int, int, int)':
mergers.cpp:34:9: error: 'i' was not declared in this scope
   34 |   marky[i]=1;
      |         ^
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++){
      |                ~^~~~~~~~~~~~~~