Submission #158156

#	Time	Username	Problem	Language	Result	Execution time	Memory
158156		username	Mergers (JOI19_mergers)	C++14	0 / 100	309 ms	114204 KiB

mergers

#pragma GCC optimize("O3")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define tr(it,a) for(auto it:a)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define umin(x,y) (x=min(x,(y)))
#define umax(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
//
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define rep(i,j,k) for(int i=(j);i<(k);++i)
#define rrep(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define all(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
 #define __debug 
#ifdef __debug
	#define ios (void)0
	#define pr(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {rep(zy,s,t)pr(a[zy]<<' ');pr(endl);}
#else
	#define ios cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define pr(...) (void)0
	#define ar(...) (void)0
#endif
//
const int maxn=5e5+9,mxlgn=20;
int n,k,cl=0,res=0,s[maxn],h[maxn],in[maxn],ex[maxn],p[mxlgn][maxn];
vector<int>g[maxn],c[maxn];

//struct dsu{
//	int fa[maxn],sz[maxn];
//	void init(int k){rep(i,0,k)fa[i]=i,sz[i]=1;}
//	int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
//	void unite(int x,int y){
//		x=find(x),y=find(y);
//		if(x==y)continue;
//		if(sz[x]>sz[y])swap(x,y);
//		fa[x]=y,sz[y]+=sz[x];
//	}
//}sol;

int isa(int u,int v){return in[u]<=in[v]&&ex[v]<=ex[u];}

int lca(int u,int v){
	if(isa(u,v))return u;
	else if(isa(v,u))return v;
	else{
		rrep(i,mxlgn,0)if(p[i][u]>=0&&!isa(p[i][u],v))u=p[i][u];
		return p[0][u];
	}
}

void dfs1(int u,int f){
	p[0][u]=f;
	in[u]=cl++;
	rep(i,0,g[u].size()){
		int v=g[u][i];
		if(v==f)continue;
		dfs1(v,u);
	}
	ex[u]=cl;
}

pii dfs2(int u,int f){
	int top=h[u],cnt=0;
	rep(i,0,g[u].size()){
		int v=g[u][i];
		if(v==f)continue;
		pii tt=dfs2(v,u);
		if(isa(tt.f,top))top=tt.f;
		cnt+=tt.s;
	}
	if(!u&&cnt==1)++res;
	if(u==top)res+=cnt<1,cnt=1;
	return {top,cnt};
}

main(){
	ios;
	cin>>n>>k;
	rep(i,1,n){
		int a,b;cin>>a>>b,--a,--b;
		g[a].pb(b),g[b].pb(a);
	}
	rep(i,0,n)cin>>s[i],--s[i],c[s[i]].pb(i);
	memset(p,-1,sizeof p);
	dfs1(0,-1);
	rep(i,0,mxlgn-1)rep(j,0,n)if(p[i][j]>=0)p[i+1][j]=p[i][p[i][j]];
	rep(i,0,k){
		int top=c[i][0];
		rep(j,1,c[i].size())top=lca(top,c[i][j]);
		rep(j,0,c[i].size())h[c[i][j]]=top;
	}
	dfs2(0,-1);
	cout<<res-1<<endl;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs1(int_fast64_t, int_fast64_t)':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
mergers.cpp:69:2: note: in expansion of macro 'rep'
  rep(i,0,g[u].size()){
  ^~~
mergers.cpp: In function 'pii dfs2(int_fast64_t, int_fast64_t)':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
mergers.cpp:79:2: note: in expansion of macro 'rep'
  rep(i,0,g[u].size()){
  ^~~
mergers.cpp: At global scope:
mergers.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
mergers.cpp: In function 'int main()':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
mergers.cpp:104:3: note: in expansion of macro 'rep'
   rep(j,1,c[i].size())top=lca(top,c[i][j]);
   ^~~
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
mergers.cpp:105:3: note: in expansion of macro 'rep'
   rep(j,0,c[i].size())h[c[i][j]]=top;
   ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30