Submission #1307953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307953		vako_p	Mergers (JOI19_mergers)	C++20	22 / 100	63 ms	29620 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " -----> " << x << endl;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int mxN = 1e6 + 5;
ll n,a[mxN],val[mxN],in[mxN],out[mxN],t,k,val1[mxN],par[mxN][20];
vector<ll> vv,v[mxN];
bool vis[mxN];

void dfs(ll at){
  for(int i = 1; i < 20; i++) par[at][i] = par[par[at][i - 1]][i - 1];
  in[at] = t++;
  for(auto it : v[at]){
    if(it == par[at][0]) continue;
    par[it][0] = at;
    dfs(it);
  }
  out[at] = t;
}

bool check(ll at, ll it){
  return (in[at] <= in[it] and out[at] >= out[it]);
}

ll lca(ll at, ll it){
  if(check(at, it)) return at;
  for(int i = 19; i >= 0; i--) if(!check(par[at][i], it)) at = par[at][i];
  return par[at][0];
}

void dfs1(ll at){
  for(auto it : v[at]){
    if(it == par[at][0]) continue;
    dfs1(it);
    val[at] = lca(val[at], val[it]);
    if(vis[it]) vis[at] = true;
  }
  if(val[at] == at and !vis[at]){
    vis[at] = true;
    vv.pb(at);
  }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n - 1; i++){
    ll x,y;
    cin >> x >> y;
    v[x].pb(y);
    v[y].pb(x);
  }
  for(int i = 1; i <= n; i++) cin >> a[i];
  par[1][0] = 1;
  dfs(1);
  for(int i = 1; i <= n; i++){
    if(val1[a[i]]) val1[a[i]] = lca(val1[a[i]], i);
    else val1[a[i]] = i;
  }
  for(int i = 1; i <= n; i++) val[i] = val1[a[i]];
  dfs1(1);
  ll ans = vv.size(),x = vv[0];
  if(ans == 1){
    cout << 0;
    return 0;
  }
  // debug(ans);
  // debug(vv[0]);
  for(int i = 1; i < vv.size(); i++) x = lca(x, vv[i]);
  if(val[x] == 1) cout << (ans + 1) / 2;
  else cout << ans / 2 + 1;
}

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