Submission #920226

#TimeUsernameProblemLanguageResultExecution timeMemory
920226KiaRezCats or Dogs (JOI18_catdog)C++17
0 / 100
5 ms19548 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 17; ll Mod = 998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } struct node { int dp[2][2]; node() {dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0; dp[0][1]=dp[1][0]=N;} } seg[N]; node merge(node x, node y) { node z; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { z.dp[i][j] = min({x.dp[i][1]+y.dp[1][j], x.dp[i][0]+y.dp[0][j], x.dp[i][0]+y.dp[1][j]+1, 1+x.dp[i][1]+y.dp[0][j]}); } } return z; } int n, tim, dwn[N], tin[N], tout[N], par[N], head[N], h[N], subt[N], typ[N]; vector<int> adj[N]; void init(int v, int p=0) { par[v]=p, h[v]=h[p]+1, subt[v]=1; for(int u : adj[v]) { if(u == p) continue; init(u, v); subt[v] += subt[u]; } } void dfs(int v, int p) { int mx = 0; tin[v] = ++tim, head[v] = p, dwn[p] = v; for(int u : adj[v]) if(u!=par[v]) mx = (subt[mx] > subt[u] ? mx : u); if(mx > 0) dfs(mx, p); for(int u : adj[v]) if(u!=par[v] && u!=mx) dfs(u, u); tout[v] = tim+1; } void update(int ind, node val) { if(ind == 0) return; if(ind >= (1<<lg)) { seg[ind] = val; } else { seg[ind] = merge(seg[2*ind], seg[2*ind+1]); } update(ind/2, val); } node query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) { if(lc>=l && rc<=r) return seg[ind]; int mid = (lc+rc)/2; if(r<=mid) return query(l, r, 2*ind, lc, mid); if(l>=mid) return query(l, r, 2*ind+1, mid, rc); return merge(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc)); } void initialize(int _n, vector<int> A, vector<int> B) { n=_n; for(int i=0; i<n-1; i++) adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]); init(1); dfs(1, 1); } int cat(int v) { typ[v] = 1; node ct; ct.dp[1][0]=ct.dp[1][1]=ct.dp[0][1]=n; update(tin[v]+(1<<lg)-1, ct); while(head[v] != 1) { ct = query(tin[head[v]], tin[dwn[head[v]]]+1); node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1); tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); v=par[head[v]]; update(tin[v]+(1<<lg)-1, tmp); } ct = query(tin[1], tin[dwn[1]]+1); return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]}); } int dog(int v) { typ[v] = 2; node ct; ct.dp[1][0]=ct.dp[0][0]=ct.dp[0][1]=n; update(tin[v]+(1<<lg)-1, ct); while(head[v] != 1) { ct = query(tin[head[v]], tin[dwn[head[v]]]+1); node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1); tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); v=par[head[v]]; update(tin[v]+(1<<lg)-1, tmp); } ct = query(tin[1], tin[dwn[1]]+1); return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]}); } int neighbor(int v) { typ[v] = 0; node ct; update(tin[v]+(1<<lg)-1, ct); while(head[v] != 1) { ct = query(tin[head[v]], tin[dwn[head[v]]]+1); node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1); tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]}); tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]}); v=par[head[v]]; update(tin[v]+(1<<lg)-1, tmp); } ct = query(tin[1], tin[dwn[1]]+1); return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]}); } /* int main () { initialize(5, {1, 2, 2, 4}, {2, 3, 4, 5}); cout<<cat(3)<<endl; cout<<dog(5)<<endl; tmp2 = merge(tmp2, tmp1); fuck(tmp2.dp[0][0]); fuck(tmp2.dp[1][0]); fuck(tmp2.dp[0][1]); fuck(tmp2.dp[1][1]); cout<<cat(2)<<endl; cout<<dog(1)<<endl; return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...