Submission #540134

#TimeUsernameProblemLanguageResultExecution timeMemory
540134PixelCatMergers (JOI19_mergers)C++14
0 / 100
123 ms27920 KiB
/* 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...