| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 376775 |
2021-03-12T03:41:31 Z |
fhvirus |
Mergers (JOI19_mergers) |
C++17 |
|
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){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
