oj.uz

Submission #152093

# Submission time Handle Problem Language Result Execution time Memory
152093 2019-09-06T11:09:35 Z arnold518 Cats or Dogs (JOI18_catdog) C++14
0 / 100
 3000 ms 9080 KB 
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 1e6;

int N;
vector<int> adj[MAXN+10];

int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10];

struct Node
{
    int AA, AB, BA, BB;
    Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {}
    Node() : AA(0), AB(0), BA(0), BB(0) {}
};

Node combine(Node lc, Node rc)
{
    Node ret;
    ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA});
    ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB});
    ret.BA=min({lc.BA+rc.AA, lc.BA+rc.BA+1, lc.BB+rc.AA+1, lc.BB+rc.BA});
    ret.BB=min({lc.BA+rc.AB, lc.BA+rc.BB+1, lc.BB+rc.AB+1, lc.BB+rc.BB});
    return ret;
}

struct SEG
{
    Node tree[MAXN*4+10];

    void update(int node, int tl, int tr, int pos, Node val)
    {
        if(tr<pos || pos<tl) return;
        if(tl==tr)
        {
            tree[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, pos, val);
        update(node*2+1, mid+1, tr, pos, val);
        tree[node]=combine(tree[node*2], tree[node*2+1]);
    }

    Node query(int node, int tl, int tr, int l, int r)
    {
        if(l<=tl && tr<=r) return tree[node];
        if(r<tl || tr<l) return Node();
        int mid=tl+tr>>1;
        return combine(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }

    void debug(int node, int tl, int tr)
    {
        printf("%d %d %d : %d %d %d %d\n", node, tl, tr, tree[node].AA, tree[node].AB, tree[node].BA, tree[node].BB);
        if(tl==tr) return;
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }
}seg;

void dfs(int now, int bef, int depth)
{
    sz[now]=1;
    par[now]=bef;
    dep[now]=depth;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, depth+1);
        sz[now]+=sz[nxt];
    }
}

void hld(int now, int bef)
{
    idx[now]=cnt++;

    int heavy=0;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(sz[heavy]<sz[nxt]) heavy=nxt;
    }

    if(heavy==0)
    {
        tail[now]=now;
        return;
    }

    head[heavy]=head[now];
    hld(heavy, now);

    for(int nxt : adj[now])
    {
        if(nxt==bef || nxt==heavy) continue;
        head[nxt]=nxt;
        hld(nxt, now);
    }

    tail[now]=tail[heavy];
}

void initialize(int _N, vector<int> A, vector<int> B)
{
    int i, j;
    N=_N;

    for(i=0; i<N-1; i++)
    {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    dfs(1, 0, 1);
    head[1]=1;
    hld(1, 0);
}

int query(int u, int val)
{
    Node chg;
    if(val==0) chg=Node(0, 0, 0, 0);
    if(val==1) chg=Node(0, INF, INF, INF);
    if(val==2) chg=Node(INF, INF, INF, 0);

    while(head[u]!=1)
    {
        int a=par[head[u]], b=head[u];
        Node qa=seg.query(1, 1, N, idx[a], idx[a]), qb=seg.query(1, 1, N, idx[head[b]], idx[tail[b]]);
        qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
        seg.update(1, 1, N, idx[u], chg);
        qb=seg.query(1, 1, N, idx[head[b]], idx[tail[b]]);
        qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
        qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
        chg=qa;
    }
    seg.update(1, 1, N, idx[u], chg);
    Node ans=seg.query(1, 1, N, idx[head[1]], idx[tail[1]]);
    //seg.debug(1, 1, N); printf("==========\n");
    return min({ans.AA, ans.AB, ans.BA, ans.BB});
}

int cat(int u)
{
    return query(u, 1);
}

int dog(int u)
{
    return query(u, 2);
}

int neighbor(int u)
{
    return query(u, 0);
}

Compilation message

catdog.cpp: In member function 'void SEG::update(int, int, int, int, Node)':
catdog.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int, int, int, int)':
catdog.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::debug(int, int, int)':
catdog.cpp:65:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:116:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Execution timed out 3052 ms 9080 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Execution timed out 3052 ms 9080 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Execution timed out 3052 ms 9080 KB Time limit exceeded
3 Halted 0 ms 0 KB -