Submission #131764

#	Time	Username	Problem	Language	Result	Execution time	Memory
131764		duality	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	816 ms	24204 KiB

catdog

#define DEBUG 1

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "catdog.h"

int n;
vi adjList[100000];
int parent[100000],size[100000],depth[100000],heavy[100000];
int chain[100000],disc[100000],head[100000],tail[100000],csize[100000];
int c = 0,num = 0;
int curr[100000],dp[100000][2];
struct node { int cc,cd,dc,dd; };
node com(node a,node b) {
    if (a.cc == -1) return b;
    else if (b.cc == -1) return a;
    node c;
    c.cc = min(min(min(a.cc+b.cc,a.cd+b.dc),min(a.cd+b.cc,a.cc+b.dc)+1),(int) 1e9);
    c.cd = min(min(min(a.cc+b.cd,a.cd+b.dd),min(a.cd+b.cd,a.cc+b.dd)+1),(int) 1e9);
    c.dc = min(min(min(a.dc+b.cc,a.dd+b.dc),min(a.dd+b.cc,a.dc+b.dc)+1),(int) 1e9);
    c.dd = min(min(min(a.dc+b.cd,a.dd+b.dd),min(a.dd+b.cd,a.dc+b.dd)+1),(int) 1e9);
    return c;
}
node tree[1 << 18];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = (node){0,(int) 1e9,(int) 1e9,0};
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = com(tree[2*i+1],tree[2*i+2]);
    return 0;
}
int update(int s,int e,int ai,int i,int c,int d) {
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        tree[i].cc += c,tree[i].dd += d;
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,ai,2*i+1,c,d),update(mid+1,e,ai,2*i+2,c,d);
    tree[i] = com(tree[2*i+1],tree[2*i+2]);
    return 0;
}
node query(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return (node){-1,-1,-1,-1};
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return com(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
pii query(int u) {
    node r = query(0,n-1,disc[head[chain[u]]],disc[tail[chain[u]]],0);
    int c = min(r.cc,r.cd),d = min(r.dc,r.dd);
    return mp(min(c,d+1),min(d,c+1));
}
int doDFS(int u,int p,int d) {
    int i;
    parent[u] = p,depth[u] = d,size[u] = 1,heavy[u] = -1;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            size[u] += doDFS(v,u,d+1);
            if ((heavy[u] == -1) || (size[v] > size[heavy[u]])) heavy[u] = v;
        }
    }
    return size[u];
}
int doHLD(int u,int p) {
    int i;
    chain[u] = c,disc[u] = num++;
    if (csize[c] == 0) head[c] = u;
    csize[c]++,tail[c] = u;
    if (heavy[u] != -1) doHLD(heavy[u],u);
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if ((v != p) && (v != heavy[u])) c++,doHLD(v,u);
    }
    return 0;
}
void initialize(int N,vector<int> A,vector<int> B) {
    int i;
    n = N;
    for (i = 0; i < N-1; i++) {
        A[i]--,B[i]--;
        adjList[A[i]].pb(B[i]);
        adjList[B[i]].pb(A[i]);
    }
    doDFS(0,-1,0),doHLD(0,-1),build(0,N-1,0);
}
int update(int u,int c,int d) {
    while (u != -1) {
        pii a = query(u);
        update(0,n-1,disc[u],0,c,d);
        pii b = query(u);
        c = b.first-a.first,d = b.second-a.second;
        u = parent[head[chain[u]]];
    }
    return 0;
}
int cat(int v) {
    v--,curr[v] = 1,update(v,0,1e9);
    pii ans = query(0);
    return min(ans.first,ans.second);
}
int dog(int v) {
    v--,curr[v] = 2,update(v,1e9,0);
    pii ans = query(0);
    return min(ans.first,ans.second);
}
int neighbor(int v) {
    v--;
    if (curr[v] == 1) update(v,0,-1e9);
    else if (curr[v] == 2) update(v,-1e9,0);
    curr[v] = 0;
    pii ans = query(0);
    return min(ans.first,ans.second);
}

Compilation message (stderr)

catdog.cpp: In function 'int doDFS(int, int, int)':
catdog.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
catdog.cpp: In function 'int doHLD(int, int)':
catdog.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~

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