oj.uz

답안 #376775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376775 2021-03-12T03:41:31 Z fhvirus Mergers (JOI19_mergers) C++17
0 / 100
 127 ms 33248 KB 
// 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);
	}
}

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

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();
	mke();

	int ans = leaf(1, -1) - 1;
	chmax(ans, 0);

	cout << ans << '\n';
	return 0;
}

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 31968 KB Output is correct
2 Incorrect 100 ms 33248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23916 KB Output isn't correct
2 Halted 0 ms 0 KB -