Submission #1172042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172042		_callmelucian	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3094 ms	9864 KiB

catdog

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
bool isCat[mn], isDog[mn];
int par[mn], dp[2][mn], n;
vector<int> adj[mn];

void dfs (int u, int p) {
    par[u] = p;
    for (int v : adj[u])
        if (v != p) dfs(v, u);
}

void initialize (int _n, vector<int> A, vector<int> B) {
    n = _n;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs(1, 1);
}

void clearContrib (int u, int v) {
//    cout << "clear-contrib " << u << "\n";
    if (par[u] != u) clearContrib(par[u], u);
    dp[0][u] -= min(isCat[v] ? INT_MAX : dp[0][v], isDog[v] ? INT_MAX : dp[1][v] + 1);
    dp[1][u] -= min(isCat[v] ? INT_MAX : dp[0][v] + 1, isDog[v] ? INT_MAX : dp[1][v]);
}

void addContrib (int u, int v) {
    dp[0][u] += min(isCat[v] ? INT_MAX : dp[0][v], isDog[v] ? INT_MAX : dp[1][v] + 1);
    dp[1][u] += min(isCat[v] ? INT_MAX : dp[0][v] + 1, isDog[v] ? INT_MAX : dp[1][v]);
    if (par[u] != u) addContrib(par[u], u);
}

int solve() { return min(isCat[1] ? INT_MAX : dp[0][1], isDog[1] ? INT_MAX : dp[1][1]); }

int cat (int u) {
    if (par[u] != u) clearContrib(par[u], u);
    isCat[u] = 1;
    if (par[u] != u) addContrib(par[u], u);
    return solve();
}

int dog (int u) {
    if (par[u] != u) clearContrib(par[u], u);
    isDog[u] = 1;
    if (par[u] != u) addContrib(par[u], u);
    return solve();
}

int neighbor (int u) {
    if (par[u] != u) clearContrib(par[u], u);
    isCat[u] = isDog[u] = 0;
    if (par[u] != u) addContrib(par[u], u);
    return solve();
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<int> A = {1, 2, 2, 4}, B = {2, 3, 4, 5};
    initialize(5, A, B);

    cout << cat(3) << " " << dog(5) << "\n";
    cout << cat(2) << " " << dog(1) << "\n";
    cout << neighbor(2) << "\n";

    return 0;
}
#endif

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