Submission #956173

#	Time	Username	Problem	Language	Result	Execution time	Memory
956173		Vladth11	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	442 ms	35484 KiB

catdog

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include "catdog.h"

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 250002;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

vector <int> v[NMAX];
int stamp;
int n;
pii timp[NMAX];
int sz[NMAX];
int maxi[NMAX];
int cpt[NMAX];
int last[NMAX];
int pa[NMAX];
int dp[NMAX][2]; /// suma vecinilor daca node e 0(cat)/1(dog)
int notAllowed[NMAX][2];

struct Node {
    int dp[2][2];
} aint[NMAX * 4];

void DFS(int node, int p) {
    sz[node] = 1;
    maxi[node] = -1;
    for(auto x : v[node]) {
        if(x == p) continue;
        DFS(x, node);
        sz[node] += sz[x];
        if(maxi[node] == -1 || sz[maxi[node]] < sz[x])
            maxi[node] = x;
    }
}

void hld(int node, int p, int capat) {
    timp[node].first = ++stamp;
    pa[node] = p;
    cpt[node] = capat;
    last[capat] = node;
    if(maxi[node] != -1) {
        hld(maxi[node], node, capat);
    }
    for(auto x : v[node]) {
        if(x == p || maxi[node] == x)
            continue;
        hld(x, node, x);
    }
    timp[node].second = stamp;
}

Node combine(Node a, Node b) {
    Node sol;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            sol.dp[i][j] = INF;
            for(int t = 0; t < 2; t++) {
                sol.dp[i][j] = min(sol.dp[i][j], a.dp[i][t] + min(b.dp[t][j], b.dp[(t ^ 1)][j] + 1));
            }
        }
    }
    return sol;
}

void update(int node, int st, int dr, int a, int realNode) {
    if(st == dr) {
        aint[node].dp[0][0] = dp[realNode][0] + notAllowed[realNode][0] * INF;
        aint[node].dp[1][1] = dp[realNode][1] + notAllowed[realNode][1] * INF;
        aint[node].dp[0][1] = aint[node].dp[1][0] = INF;
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, realNode);
    else
        update(node * 2 + 1, mid + 1, dr, a, realNode);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]); /// numar mai mic => preordine primul => capatul lantului
}

Node query(int node, int st, int dr, int a, int b) {
    if(a <= st && dr <= b)
        return aint[node];
    int mid = (st + dr) / 2;
    if(b <= mid) {
        return query(node * 2, st, mid, a, b);
    }
    if(a > mid) {
        return query(node * 2 + 1, mid + 1, dr, a, b);
    }
    return combine(query(node * 2, st, mid, a, b), query(node * 2 + 1, mid + 1, dr, a, b));
}

pii realValue(int node) {
    Node x = query(1, 1, n, timp[node].first, timp[last[cpt[node]]].first);
    return {min(x.dp[0][1], x.dp[0][0]), min(x.dp[1][0], x.dp[1][1])};
}



void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(int i = 0; i < A.size(); i++) {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }
    DFS(1, 0);
    hld(1, 0, 1);
    for(int i = 1; i <= n; i++) {
        /// aici nu avem ce adauga
        update(1, 1, n, timp[i].first, i); /// = {0, 0}
    }
}

void adauga(int node, int sgn) {
    vector <pii> perechi;
    while(pa[cpt[node]] != 0) {
        int unde = pa[cpt[node]];
        int cine = cpt[node];
        perechi.push_back({unde, cine});
        node = unde;
    }
    if(sgn == -1) reverse(perechi.begin(), perechi.end());
    for(auto x : perechi) {
        int unde = x.first;
        int cine = x.second;
        pii am = realValue(cine);
        dp[unde][0] += sgn * min(am.first, am.second + 1);
        dp[unde][1] += sgn * min(am.first + 1, am.second);
        update(1, 1, n, timp[unde].first, unde);
    }
}

int cat(int v) {
    adauga(v, -1);
    notAllowed[v][1] = 1;
    update(1, 1, n, timp[v].first, v);
    adauga(v, 1);
    pii sol = realValue(1);
    return min(sol.first, sol.second);
}

int dog(int v) {
    adauga(v, -1);
    notAllowed[v][0] = 1;
    update(1, 1, n, timp[v].first, v);
    adauga(v, 1);
    pii sol = realValue(1);
    return min(sol.first, sol.second);
}

int neighbor(int v) {
    adauga(v, -1);
    notAllowed[v][0] = notAllowed[v][1] = 0;
    update(1, 1, n, timp[v].first, v);
    adauga(v, 1);
    pii sol = realValue(1);
    return min(sol.first, sol.second);
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0; i < A.size(); i++) {
      |                    ~~^~~~~~~~~~

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