Submission #558819

#	Time	Username	Problem	Language	Result	Execution time	Memory
558819		RaresFelix	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	2 ms	2656 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define MN 100071

using namespace std;

///DEBUG

string to_string(string s) {
    return '"' + s + '"';
}
string to_string(const char *s) {
    return to_string((string) s);
}
string to_string(bool b) {
    return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using state = pair<int, int>;
const int INF = 1e9;
const state CAT = {0, 1};
const state DOG = {1, 0};
const state EMPTY = {0, 0};

vector<int> L[MN];
int Sz[MN], HeavySon[MN], Nxt[MN];
int Par[MN], n;
int tmr, In[MN], Out[MN];
state Surplus[MN];

namespace AINT {
    state V[4 * MN];
    inline state uni(const state &a, const state &b) {
        return make_pair(min({a.first + b.first, a.second + 1 + b.first, INF}), min({a.second + b.second, a.first + 1 + b.second, INF}));
    }
    void update(int p, state v, int u = 1, int s = 1, int d = tmr) {
        if(d < p || p < s) return;
        if(s == d) {
            debug(u, s, d, p, v, Surplus[p], V[u]);
            V[u] = v;
            V[u].first += Surplus[p].first;
            V[u].second += Surplus[p].second;
            V[u].first = min(V[u].first, INF);
            V[u].second = min(V[u].second, INF);
            debug(V[u]);
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = uni(V[u << 1], V[u << 1 | 1]);
        debug(u, V[u]);
    }
    state query(int l, int r, int u = 1, int s = 1, int d = tmr) {
        if(r < s || d < l) return {0, 0}; //nil
        if(l <= s && d <= r) return V[u];
        return uni(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
    }
}

void dfs_sz(int u, int p, int pp) {
    Sz[u] = 1;
    for(auto &it : L[u])
        if(it != p)  {
            dfs_sz(it, u, p), Sz[u] += Sz[it];
            if(Sz[it] > Sz[L[u][0]] || L[u][0] == p) swap(it, L[u][0]);
        }
}

void dfs_assign(int u, int p) {
    In[u] = ++tmr;
    Par[u] = p;
    if(p) Nxt[u] = (L[p][0] == u ? Nxt[p] : u);
    else Nxt[u] = u;
    Out[Nxt[u]] = tmr;
    for(auto it : L[u])
        if(it != p) dfs_assign(it, u);
    debug(u, In[u], Par[u], Nxt[u], Out[Nxt[u]], Sz[u]);
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(int i = 0; i < int(A.size()); ++i)
        L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
    dfs_sz(1, 0, 0);
    dfs_assign(1, 0);
}

void emul_prop(int u, stack<state> &UV) {
    if(!u) return;
    int head = Nxt[u];
    int tail = Out[head];
    int parinte_lant = Par[head];
    emul_prop(parinte_lant, UV);
    UV.push(AINT::query(In[head], tail));
}

state ValHut[MN];

void propag(int u, stack<state> &UltVal) { // va propaga in HLD update-ul facut asupra lui u
    if(!u) return;
    int head = Nxt[u];
    int tail = Out[head];
    state ls = UltVal.top(); UltVal.pop();
    state now = AINT::query(In[head], tail);
    state delta = {now.first - ls.first, now.second - ls.second};
    int parinte_lant = Par[head];
    debug(u, head, tail, parinte_lant, ls, now, delta, Surplus[parinte_lant]);
    Surplus[parinte_lant].first += delta.first;
    Surplus[parinte_lant].second += delta.second;
    AINT::update(parinte_lant, ValHut[parinte_lant]); // il modific doar la surplus
    propag(parinte_lant, UltVal);
}
int rez() {
    state re = Surplus[0];
    return min(re.first, re.second);
}

int cat(int v) {
    debug("up0 pisi", v);
    ValHut[v] = CAT;
    stack<state> Old;
    emul_prop(v, Old);
    AINT::update(In[v], CAT);
    propag(v, Old);
    return rez();
}

int dog(int v) {
    debug("up0 caine", v);
    ValHut[v] = DOG;
    stack<state> Old;
    emul_prop(v, Old);
    AINT::update(In[v], DOG);
    propag(v, Old);
    return rez();
}

int neighbor(int v) {
    debug("up0 afara", v, ValHut[v]);
    ValHut[v] = EMPTY;
    stack<state> Old;
    emul_prop(v, Old);
    AINT::update(In[v], EMPTY);
    propag(v, Old);
    return rez();
}

Compilation message (stderr)

catdog.cpp: In function 'void AINT::update(int, state, int, int, int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:73:13: note: in expansion of macro 'debug'
   73 |             debug(u, s, d, p, v, Surplus[p], V[u]);
      |             ^~~~~
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:79:13: note: in expansion of macro 'debug'
   79 |             debug(V[u]);
      |             ^~~~~
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:85:9: note: in expansion of macro 'debug'
   85 |         debug(u, V[u]);
      |         ^~~~~
catdog.cpp: In function 'void dfs_assign(int, int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:111:5: note: in expansion of macro 'debug'
  111 |     debug(u, In[u], Par[u], Nxt[u], Out[Nxt[u]], Sz[u]);
      |     ^~~~~
catdog.cpp: In function 'void propag(int, std::stack<std::pair<int, int> >&)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:141:5: note: in expansion of macro 'debug'
  141 |     debug(u, head, tail, parinte_lant, ls, now, delta, Surplus[parinte_lant]);
      |     ^~~~~
catdog.cpp: In function 'int cat(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:153:5: note: in expansion of macro 'debug'
  153 |     debug("up0 pisi", v);
      |     ^~~~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:163:5: note: in expansion of macro 'debug'
  163 |     debug("up0 caine", v);
      |     ^~~~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:50:20: warning: statement has no effect [-Wunused-value]
   50 | #define debug(...) 42
      |                    ^~
catdog.cpp:173:5: note: in expansion of macro 'debug'
  173 |     debug("up0 afara", v, ValHut[v]);
      |     ^~~~~

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