Submission #328551

#	Time	Username	Problem	Language	Result	Execution time	Memory
328551		YJU	Capital City (JOI20_capital_city)	C++14	Compilation error	0 ms	0 KiB

capital_city

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,x,y,col[N],maxn[N],vis[N],sub[N],vis_col[N],ans=INF;
vector<ll> v[N],C[N];
ll pa[N],tag[N];

ll Find_root(ll nd){
	function<void(ll,ll)> DFS = [&](ll id,ll p){
		sub[id]=1;maxn[id]=-1;
		for(auto i:v[id]){
			if(i!=p&&!vis[i]){
				DFS(i,id);
				sub[id]+=sub[i];
				if(maxn[id]==-1||sub[maxn[id]]<sub[i])maxn[id]=i;
			}
		}
	};
	DFS(nd,0);
	ll tot=sub[nd];
	while(maxn[nd]!=-1&&sub[maxn[nd]]*2>=tot)nd=maxn[nd];
	return nd;
}

void centroid(ll nd){
	ll rt=Find_root(nd);
	function<void(ll,ll)> DFS = [](ll id,ll p){
		pa[id]=p;tag[id]=rt;
		for(auto i:v[id]){
			if(!vis[i]&&i!=p)DFS(i,id);
		}
	};
	DFS(rt,rt);
	vector<ll> res;
	queue<ll> q;
	q.push(rt);
	ll cnt=-1,ok=1,u;
	while(SZ(q)&&ok){
		u=q.front();q.pop();
		++cnt;
		while(ok){
			if(tag[u]==0)break;
			if(!vis_col[col[u]]){
				cnt-=SZ(C[col[u]]);
				vis_col[col[u]]=1;
				res.pb(col[u]);
				for(auto i:C[col[u]]){
					q.push(i);
					if(tag[i]!=rt){
						ok=0;break;
					}
				}
			}
			tag[u]=0;
			u=pa[u];
			if(u==rt)break;
		}
	}
	for(auto i:res)vis_col[i]=0;
	if(cnt==0)ans=min(ans,SZ(res)-1);
	vis[u]=1;
	for(auto i:v[u])if(!vis[i])centroid(i);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,n-1)cin>>x>>y,v[x].pb(y),v[y].pb(x);
	REP1(i,n)cin>>col[i],C[col[i]].pb(i);
	centroid(1);
	cout<<ans<<"\n"; 
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In lambda function:
capital_city.cpp:48:20: error: 'rt' is not captured
   48 |   pa[id]=p;tag[id]=rt;
      |                    ^~
capital_city.cpp:47:31: note: the lambda has no capture-default
   47 |  function<void(ll,ll)> DFS = [](ll id,ll p){
      |                               ^
capital_city.cpp:46:5: note: 'll rt' declared here
   46 |  ll rt=Find_root(nd);
      |     ^~
capital_city.cpp:50:21: error: 'DFS' is not captured
   50 |    if(!vis[i]&&i!=p)DFS(i,id);
      |                     ^~~
capital_city.cpp:47:31: note: the lambda has no capture-default
   47 |  function<void(ll,ll)> DFS = [](ll id,ll p){
      |                               ^
capital_city.cpp:47:24: note: 'std::function<void(long long int, long long int)> DFS' declared here
   47 |  function<void(ll,ll)> DFS = [](ll id,ll p){
      |                        ^~~