Submission #540134

#	Time	Username	Problem	Language	Result	Execution time	Memory
540134		PixelCat	Mergers (JOI19_mergers)	C++14	0 / 100	123 ms	27920 KiB

mergers

/* code by the cute ~~Dengdualang~~ PixelCat owo */
/*     as cute as nacho neko (aka. my wife)!     */

/*     Nhade stay for a night here               */
/*     183234 deng deng deng pixelcat oops       */
/*     (yang wang yesu)*2                        */
/*     ^ some weird stuff. nvm =w=               */

#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using LLL = __int128_t;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1e9 + 7)
#define INF (int)(4e18)  // 9e18
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p >>= 1;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

vector<int> adj[500050];
int s[500050];
int tot[500050];

struct OWO{
    int oao;
    map<int,int> cnt;
    OWO(): oao(0), cnt(){}
    void add(int k,int x){
        if(cnt.count(k)) oao-=(cnt[k]!=tot[k]);
        cnt[k]+=x;
        oao+=(cnt[k]!=tot[k]);
    }
    bool check(){
        return oao==0;
    }
};
void merge(OWO &a,OWO &b){
    if(sz(a.cnt)<sz(b.cnt)){
        swap(a.oao,b.oao);
        swap(a.cnt,b.cnt);
    }
    for(auto &p:b.cnt){
        a.add(p.F,p.S);
    }
}

int thonk[500050];

void dfs(int n,int p,OWO &owo){
    owo.add(s[n],1);
    for(auto &i:adj[n]) if(i!=p){
        OWO o2;
        dfs(i,n,o2);
        merge(owo,o2);
    }
    if(owo.check()) thonk[n]=1;
    // debug(n,p);
    // debug(owo.oao);
    // debug(owo.cnt);
}

int nowid=0;
int id[500050];
int deg[500050];
void build(int n,int p){
    if(thonk[n]){
        nowid++;
        id[n]=nowid;
        deg[id[n]]++;
        deg[id[p]]++;
    }
    else id[n]=id[p];
    for(auto &i:adj[n]) if(i!=p) build(i,n);
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n,m; cin>>n>>m;
    For(i,1,n-1){
        int a,b; cin>>a>>b;
        adj[a].eb(b);
        adj[b].eb(a);
    }
    For(i,1,n){
        cin>>s[i];
        tot[s[i]]++;
    }
    OWO owo;
    dfs(1,1,owo);
    build(1,1);
    int ans=0;
    For(i,1,nowid) ans+=(deg[i]==1);
    cout<<(ans+1)/2<<"\n";
    return 0;
}

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