Submission #96033

#	Time	Username	Problem	Language	Result	Execution time	Memory
96033		onjo0127	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	277 ms	32116 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e9;

struct node {
    ll cc, cd, dc, dd;
};

struct segtree {
    vector<node> tree;
    segtree(int N) {
        tree = vector<node>(4*N, {0, INF, INF, 0});
    }
    void pull(int idx) {
        node l = tree[idx*2], r = tree[idx*2+1];
        tree[idx].cc = min({l.cc + r.cc, l.cc + 1 + r.dc, l.cd + 1 + r.cc, l.cd + r.dc});
        tree[idx].cd = min({l.cc + r.cd, l.cc + 1 + r.dd, l.cd + 1 + r.cd, l.cd + r.dd});
        tree[idx].dc = min({l.dc + r.cc, l.dc + 1 + r.dc, l.dd + 1 + r.cc, l.dd + r.dc});
        tree[idx].dd = min({l.dc + r.cd, l.dc + 1 + r.dd, l.dd + 1 + r.cd, l.dd + r.dd});
    }
    void upd(int idx, int s, int e, int p, ll cat, ll dog) {
        if(p < s || e < p) return;
        if(s == e) {
            tree[idx] = {cat, INF, INF, dog};
            return;
        }
        int m = s+e >> 1;
        upd(idx*2, s, m, p, cat, dog);
        upd(idx*2+1, m+1, e, p, cat, dog);
        pull(idx);
    }
};

int A[100009];
ll C[100009], D[100009];
vector<int> adj[100009];
vector<segtree> seg;
vector<vector<int> > paths;
int sz[100009], pid[100009], vid[100009];

int dfs(int x, int p) {
    int s = 1;
    for(auto& it: adj[x]) if(it != p) s += dfs(it, x);
    return sz[x] = s;
}

void makeHLD(int x, int p) {
    if(2*sz[x] >= sz[p] && x != 1) {
        pid[x] = pid[p];
        vid[x] = vid[p] + 1;
        paths[pid[x]].push_back(x);
    }
    else {
        pid[x] = paths.size();
        vid[x] = 1;
        paths.push_back({p, x});
    }
    for(auto& it: adj[x]) if(it != p) makeHLD(it, x);
}

void updHLD(int u, ll cat, ll dog) {
    int pd = pid[u], vd = vid[u], rtp = paths[pd][0], rt = paths[pd][1];
    node& srt = seg[pd].tree[1];
    ll crt = min(srt.cc, srt.cd), drt = min(srt.dc, srt.dd);
    C[rtp] -= min(crt, drt + 1);
    D[rtp] -= min(crt + 1, drt);
    seg[pd].upd(1, 1, (int)paths[pd].size() - 1, vd, cat, dog);
    crt = min(srt.cc, srt.cd); drt = min(srt.dc, srt.dd);
    C[rtp] += min(crt, drt + 1);
    D[rtp] += min(crt + 1, drt);
    if(rtp != 0) updHLD(rtp, (A[rtp] == 2 ? INF : C[rtp]), (A[rtp] == 1 ? INF : D[rtp]));
}

void initialize(int N, vector<int> A, vector<int> B) {
    for(int i=0; i<N-1; i++) {
        int u = A[i], v = B[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    makeHLD(1, 0);
    for(auto& it: paths) seg.push_back(segtree(it.size() - 1));
}

int ans() {
    node& srt = seg[0].tree[1];
    ll crt = min(srt.cc, srt.cd), drt = min(srt.dc, srt.dd);
    return (int)min((A[1] == 2 ? INF : crt), (A[1] == 1 ? INF : drt));
}

int cat(int v) {
    A[v] = 1;
    updHLD(v, C[v], 1e9);
    return ans();
}

int dog(int v) {
    A[v] = 2;
    updHLD(v, 1e9, D[v]);
    return ans();
}

int neighbor(int v) {
    A[v] = 0;
    updHLD(v, C[v], D[v]);
    return ans();
}

Compilation message (stderr)

catdog.cpp: In member function 'void segtree::upd(int, int, int, int, ll, ll)':
catdog.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
catdog.cpp: In function 'void updHLD(int, ll, ll)':
catdog.cpp:65:55: warning: unused variable 'rt' [-Wunused-variable]
     int pd = pid[u], vd = vid[u], rtp = paths[pd][0], rt = paths[pd][1];
                                                       ^~

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