Submission #623904

#	Time	Username	Problem	Language	Result	Execution time	Memory
623904		urosk	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	242 ms	46796 KiB

catdog

#include "catdog.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 200005
ll n;
vector<ll> g[maxn];
ll ls[maxn],rs[maxn],root[maxn];
ll tsz = 0;
ll lik[maxn];
ll up[maxn],sub[maxn],in[maxn],csz[maxn],dpt[maxn],parent[maxn];
ll timer = 0;
struct node{
    ll a[2][2];
    void init(){a[0][0] = a[1][1] = 0; a[0][1] = a[1][0] = llinf;}
    node(){init();}
};
node t[4*maxn];
node mrg(node a,node b){
    node c;
    for(ll i = 0;i<=1;i++){
        for(ll j = 0;j<=1;j++){
            c.a[i][j] = llinf;
            for(ll k = 0;k<=1;k++){
                for(ll l = 0;l<=1;l++){
                    c.a[i][j] = min(c.a[i][j],a.a[i][k]+b.a[l][j] + (k^l));
                }
            }
        }
    }
    return c;
}
void dfs_siz(ll u,ll par){
    sub[u] = 1; dpt[u] = dpt[par] + 1; parent[u] = par;
    for(ll s : g[u]) if(s!=par) dfs_siz(s,u),sub[u]+=sub[s];
}
void dfs(ll u,ll par){
    if(!up[u]) up[u] = u;
    ll smax = 0;
    for(ll s : g[u]){
        if(s==par) continue;
        if(sub[smax]<sub[s]) smax = s;
    }
    if(smax==0) return;
    up[smax] = up[u];
    dfs(smax,u);
    for(ll s : g[u]){
        if(s==par||s==smax) continue;
        dfs(s,u);
    }
}
void upd(ll &v,ll tl,ll tr,ll i,ll a,ll b){
    if(!v) v = ++tsz;
    if(tl==tr){t[v].a[0][0]+=a;t[v].a[1][1]+=b;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,a,b);
    else upd(rs[v],mid+1,tr,i,a,b);
    t[v] = mrg(t[ls[v]],t[rs[v]]);
}
pll val(ll v){
    ll a = min(t[v].a[0][0],t[v].a[0][1]);
    ll b = min(t[v].a[1][0],t[v].a[1][1]);
    a = min(a,b+1);
    b = min(b,a+1);
    return {a,b};
}
void upd(ll u,ll a,ll b){
    ll lb,la,nb,na;
    while(u){
        pll p = val(root[up[u]]);
        la = p.fi; lb = p.sc;
        upd(root[up[u]],1,csz[up[u]],dpt[u]-dpt[up[u]]+1,a,b);
        p = val(root[up[u]]);
        na = p.fi; nb = p.sc;
        u = parent[up[u]];
        a = na - la; b = nb - lb;
    }
}
ll rez(){pll p = val(root[1]); return min(p.fi,p.sc);}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(ll i = 0;i<n-1;i++){
        ll x = A[i],y = B[i];
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs_siz(1,0); dfs(1,0);
    for(ll i = 1;i<=n;i++) csz[up[i]]++;
}

int cat(int v) {
    upd(v,n,0);
    lik[v] = 1;
    return rez();
}
int dog(int v) {
    upd(v,0,n);
    lik[v] = 2;
    return rez();
}
int neighbor(int v) {
    if(lik[v]==1) upd(v,-n,0);
    else upd(v,0,-n);
    lik[v] = 0;
    return rez();
}
/*
5
1 2
2 3
2 4
4 5
5
2 3
1 5
2 2
1 1
3 2
out:
0
1
0
2
1
*/

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62