Submission #575067

#	Time	Username	Problem	Language	Result	Execution time	Memory
575067		MohammadAghil	Mergers (JOI19_mergers)	C++14	0 / 100	110 ms	40840 KiB

mergers

      #include <bits/stdc++.h>
  #pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5+5, lg = 20, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int st[maxn], par[maxn][lg], h[maxn], vl[maxn];
vector<int> adj[maxn], ct[maxn];

void dfs(int r, int p){
     par[r][0] = p;
     rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
     for(int c: adj[r]) if(c - p) h[c] = h[r] + 1, dfs(c, r);
}

int lca(int u, int v){
     if(h[u] > h[v]) swap(u, v);
     per(i,lg-1,0) if(h[par[v][i]] >= h[u]) v = par[v][i];
     if(u == v) return u;
     per(i,lg-1,0) if(par[u][i] - par[v][i]) u = par[u][i], v = par[v][i];
     return par[u][0];
}

int dfs2(int r, int p){
     int res = 0;
     for(int c: adj[r]) if(c - p){
          res += dfs2(c, r);
          st[r] += st[c];
     }
     if(st[r] || !r) return vl[r] = -1, res;
     st[r] = res;
     return res + 1;
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int n, k; cin >> n >> k;
     rep(i,1,n){
          int u, v; cin >> u >> v; u--, v--;
          adj[u].pb(v), adj[v].pb(u);
     } dfs(0, 0);
     rep(i,0,n){
          int t; cin >> t; t--;
          ct[t].pb(i);
     }
     rep(i,0,k){
          int lc = ct[i].back();
          for(int c: ct[i]) lc = lca(lc, c);
          for(int c: ct[i]) st[c]++, st[lc]--;
     }
     int ans = 1, tot = dfs2(0, 0); er(tot);
     rep(i,0,n) if(vl[i] + 1 && (vl[i] == tot-1 || vl[i] == 0)) ans++;
     cout << ans/2 << '\n';
     return 0; 
}

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