제출 #376784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376784		fhvirus	Mergers (JOI19_mergers)	C++17	100 / 100	976 ms	104420 KiB

mergers

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr<<endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr<<*a<<" \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
const int N = 5e5 + 225;
int n, k;
vector<pii> adj[N];
int lst[N];

int low[N], pre[N], tot;
void tarjan(int u, int p){
	low[u] = pre[u] = ++tot;
	int cnt = -1;
	for(int i = 0; i < adj[u].size(); ++i){
		auto &[v, e] = adj[u][i];
		if(v == p and cnt == -1){ cnt = i; continue;}
		if(pre[v] == 0){
			tarjan(v, u);
			chmin(low[u], low[v]);
			if(low[v] == pre[v])
				e = 1;
		}
		else if(pre[v] < pre[u])
			chmin(low[u], pre[v]);
	}
	if(low[u] == pre[u] && cnt != -1)
		adj[u][cnt].ss = 1;
}

int mp[N];

void dfs(int u, int id){
	mp[u] = id;
	for(auto [v, e]: adj[u]){
		if(e) continue;
		if(mp[v]) continue;
		dfs(v, id);
	}
}

int bccnt = 0;
void uni(){
	FOO(i,1,n){
		if(mp[i] == 0){
			dfs(i, ++bccnt);
		}
	}
}

vector<int> G[N];

void mke(){
	FOO(i,1,n){
		for(auto [v, e]: adj[i])
			if(e){
				G[mp[i]].pb(mp[v]);
			}
	}
}

int leaf(int u, int p){
	int ans = 0;
	for(int v: G[u])
		if(v != p)
		ans += leaf(v, u);
	if(G[u].size() <= 1) ++ans;
	return ans;
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(int a, b, i = 1; i < n; ++i){
		cin >> a >> b;
		adj[a].pb(b, 0);
		adj[b].pb(a, 0);
	}
	for(int i = 1; i <= n; ++i){
		int c; cin >> c;
		if(lst[c] != 0){
			adj[i].pb(lst[c], 0);
			adj[lst[c]].pb(i, 0);
		}
		lst[c] = i;
	}

	tarjan(1, -1);

	uni();

	if(bccnt == 1){
		cout << 0;
		return 0;
	}
	mke();

	int ans = leaf(1, -1);

	cout << (ans + 1) / 2;

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'void tarjan(int, int)':
mergers.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < adj[u].size(); ++i){
      |                 ~~^~~~~~~~~~~~~~~

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