Submission #637844

#	Time	Username	Problem	Language	Result	Execution time	Memory
637844		fatemetmhr	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	754 ms	30656 KiB

catdog

//  ~Be name khoda~  //
 
#include "catdog.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  4e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;
 
int n, id[maxn5], ti = -1, top[maxn5], par[maxn5];
int retnode[maxn5], a[maxn5], av[maxn5][3], big[maxn5];
int sz[maxn5], ans = 0;
vector <int> adj[maxn5];

struct catdog{
    int add[3], fnres[3];
    bool empty;
    catdog(){
        empty = false;
        add[0] = add[1] = add[2] = fnres[1] = fnres[2] = fnres[0] = 0;
    }
} seg[maxnt], empty_node, res;

catdog operator +(catdog a, catdog b){
    if(a.empty)
        return b;
    if(b.empty)
        return a;
    for(int i = 0; i < 3; i++){
        res.fnres[i] = b.fnres[a.fnres[i]];
        res.add[i] = b.add[a.fnres[i]] + a.add[i];
        //cout << "ok " << i << ' ' << res.fnres[i] << ' ' << res.add[i] << ' ' << a.fnres[i] << ' ' << b.fnres[i] << endl;
    }
    return res;
}

void update(int l, int r, int id, int v){
    if(r - l == 1){
        //cout << "allright " << id << ' ' << a[id] << ' ' << av[id][1] << ' ' << av[id][2] << endl;
        if(a[l] == 1){
            seg[v].fnres[0] = seg[v].fnres[1] = seg[v].fnres[2] = 1;
            seg[v].add[0] = seg[v].add[1] = seg[v].add[2] = av[l][2];
            seg[v].add[2]++;
        }
        if(a[l] == 2){
            seg[v].fnres[0] = seg[v].fnres[1] = seg[v].fnres[2] = 2;
            seg[v].add[0] = seg[v].add[1] = seg[v].add[2] = av[l][1];
            seg[v].add[1]++;
        }
        if(a[l] == 0){
            for(int i = 0; i < 3; i++){
                av[l][i]++;
                if(av[l][1] < av[l][2]){
                    seg[v].fnres[i] = 2;
                    seg[v].add[i] = av[l][1];
                }
                if(av[l][1] > av[l][2]){
                    seg[v].fnres[i] = 1;
                    seg[v].add[i] = av[l][2];
                }
                if(av[l][1] == av[l][2]){
                    seg[v].fnres[i] = 0;
                    seg[v].add[i] = av[l][1];
                }
                av[l][i]--;
            }
     
        }
        /*
        for(int i = 0; i < 3; i++)
            cout << seg[v].fnres[i] << ' ' << seg[v].add[i] << endl;
        cout << "done ans return" << endl;
        */
        return;
    }

    int mid = (l + r) >> 1;
    if(id < mid){
        update(l, mid, id, v * 2);
        //cout << "all here" << endl;
    }
    else{
        update(mid, r, id, v * 2 + 1);
        //cout << "all there" << endl;
    }
    seg[v] = seg[v * 2 + 1] + seg[v * 2];
    //cout << "ask" << ' ' << l << ' ' << r << endl;
    /*
    cout << "update of " << l << ' ' << r << ' ' << id << ' ' << v << endl;
    for(int i = 0; i < 3; i++)
        cout << seg[v].fnres[i] << ' ' << seg[v].add[i] << endl;
    //cout << "done with " << l << ' ' << r << endl;
    */
    return;
}

catdog get(int l, int r, int lq, int rq, int v){
    if(rq <= l || r <= lq)
        return empty_node;
    if(lq <= l && r <= rq){
        /*
        cout << "getting " << l << ' ' << r << ' ' << lq << ' ' << rq << endl;
        for(int i = 0; i < 3; i++)
            cout << seg[v].fnres[i] << ' ' << seg[v].add[i] << endl;
        */
        return seg[v];
    }
    int mid = (l + r) >> 1;
    res = get(mid, r, lq, rq, v * 2 + 1) + get(l, mid, lq, rq, v * 2);
    /*
    cout << "getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << mid << endl;
    for(int i = 0; i < 3; i++)
        cout << res.fnres[i] << ' ' << res.add[i] << endl;
    */
    return res;
}

void build(int l, int r, int v){
    if(r - l == 1){
        seg[v].fnres[1] = 1;
        seg[v].fnres[2] = 2;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, v * 2);
    build(mid, r, v * 2 + 1);
    seg[v] = seg[v * 2 + 1] + seg[v * 2];
    return;
}
 
void upd(int v){
    //cout << "updating " << v << ' ' << top[v] << ' ' << par[top[v]] << ' ' << id[v] << ' ' << id[top[v]] << ' ' << id[retnode[top[v]]] << endl;
    auto last = get(0, n, id[top[v]], id[retnode[top[v]]] + 1, 1);
    ans -= last.add[0];
    update(0, n, id[v], 1);
    //cout << "done with function" << endl;
    auto cur = get(0, n, id[top[v]], id[retnode[top[v]]] + 1, 1);
    ans += cur.add[0];
    //cout << "having a problem " << last.add[0] << ' ' << cur.add[0] << ' ' << ans << endl;
    if(par[top[v]] == -1)
        return;
    av[id[par[top[v]]]][last.fnres[0]]--;
    av[id[par[top[v]]]][cur.fnres[0]]++;
    upd(par[top[v]]);
}

void dfs_det(int v){
    sz[v] = 1;
    big[v] = -1;
    for(auto u : adj[v]) if(u != par[v]){
        par[u] = v;
        dfs_det(u);
        sz[v] += sz[u];
        if(big[v] == -1 || sz[u] > sz[big[v]])
            big[v] = u;
    }
    return;
}

void dfs_hld(int v){
    id[v] = ++ti;
    retnode[top[v]] = v;
    if(big[v] == -1)
        return;
    top[big[v]] = top[v];
    dfs_hld(big[v]);
    for(auto u : adj[v]) if(u != big[v] && u != par[v]){
        top[u] = u;
        dfs_hld(u);
    }
    return;
}

int cat(int v) {
    v--;
    a[id[v]] = 1;
    upd(v);
    return ans;
}
 
int dog(int v) {
    v--;
    a[id[v]] = 2;
    upd(v);
    return ans;
}
 
int neighbor(int v) {
    v--;
    a[id[v]] = 0;
    upd(v);
    return ans;
}
 
void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    empty_node.empty = true;
    build(0, n, 1);
    for(int i = 0; i < n - 1; i++){
        A[i]--; B[i]--;
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
    }
    par[0] = -1;
    dfs_det(0);
    dfs_hld(0);
    return;
}

/*
5
1 2
2 3
2 4
4 5
5
1 3
2 5
1 2
2 1
3 2
*/

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