oj.uz

Submission #884086

# Submission time Handle Problem Language Result Execution time Memory
884086 2023-12-06T15:45:41 Z activedeltorre Cats or Dogs (JOI18_catdog) C++14
38 / 100
 3000 ms 15904 KB 
#include "catdog.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
 
using namespace std;
 
const int nmax = 1e5 + 5;
const int inf = 1e6 + 5;
 
namespace Tree {
    vector<int> g[nmax];
 
    int area[nmax];
    int pch[nmax], lastpoz[nmax], p[nmax];
    int pin[nmax], pout[nmax], inp = 1;
 
    int nodepoz(int node) { return pin[node];}
 
    namespace Init {
        void preinit(int node, int f) {
            p[node] = f;
            area[node] = 1;
            for(auto x : g[node]) {
                if(x == f) continue;
                preinit(x, node);
                area[node] += area[x];
            }
            return;
        }
 
        void init(int node, int f) {
            lastpoz[pch[node]] = inp;
            pin[node] = inp++;
            int mx = -1;
            for(auto x : g[node]) {
                if(x == f) continue;
                mx = mx == -1 || area[mx] < area[x]? x : mx;
            }
            if(mx == -1) {pout[node] = inp - 1; return; }
            pch[mx] = pch[node];
            init(mx, node);
 
            for(auto x : g[node]) {
               if(x == f || x == mx) continue;
               pch[x] = x;
               init(x, node);
            }
        }
    }
 
    struct Mat {
        int mat[2][2];
        Mat() { for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) mat[i][j] = inf; }
        Mat operator +(const Mat& x) const {
            if(mat[0][0] == 0 && mat[1][1] == 0 && mat[0][1] == inf && mat[1][0] == inf) return x;
            if(x.mat[0][0] == 0 && x.mat[1][1] == 0 && x.mat[0][1] == inf && x.mat[1][0] == inf) return *this;
//            if(x == ok) return *this;
            Mat rez;
 
            for(int L = 0; L < 2; L++) {
                for(int M1 = 0; M1 < 2; M1++) {
                        for(int R = 0; R < 2; R++) {
                            rez.mat[L][R] = min(rez.mat[L][R], mat[L][M1] + min(x.mat[M1][R], x.mat[M1 ^ 1][R] + 1));
                        }
                    }
            }
 
            return rez;
        }
    };
                Mat ok;
 
 
    #define Node Mat
    namespace aint {
        Node aint[nmax * 2];
        int n;
        Node ID;
        void init(int _n, Node id) {
            ID = id;
            n = _n;
            for(int i= 0; i < 2 * n + 2; i++)
                aint[i] = id;
        }
 
        void push(int node, int L) {;}
        void upd(int p, Node x, int node, int cl, int cr) {
            if(p < cl || cr < p) return;
            if(cl == cr) { aint[node] = x; return; }
            int mid = cl + cr >> 1;
            upd(p, x, node + 1, cl, mid);
            upd(p, x, node + (mid - cl + 1) * 2, mid + 1, cr);
            aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
    //        cerr << cl << ' ' << cr << " :: \t" << aint[node].mat[0][0] << ' ' << aint[node].mat[1][1] << '\n'
        }
        Node query(int l, int r, int node, int cl, int cr) {
            if(r < cl || cr < l) return ID;
            if(l <= cl && cr <= r) return aint[node];
            int mid = cl + cr >> 1;
            return query(l, r, node + 1, cl, mid) + query(l, r, node + (mid - cl + 1) * 2, mid + 1, cr);
        }
 
        void upd(int p, Node x) { upd(p, x, 1, 1, n); }
        Node query(int l, int r) { return query(l, r, 1, 1, n); }
 
 
    };
    #undef Node
 
 
 
    struct SimpleDir {
        int red, blue;
        SimpleDir(int a = 0, int b = 0): red(a), blue(b) {;}
        SimpleDir operator +=(const SimpleDir& x) { return *this = SimpleDir(red + min(x.red, x.blue + 1), blue + min(x.blue, x.red + 1)); }
        SimpleDir operator -=(const SimpleDir& x) { return *this = SimpleDir(red - min(x.red, x.blue + 1), blue - min(x.blue, x.red + 1)); }
    };
 
    SimpleDir overson[nmax], mine[nmax];
 
    int color[nmax];
 
    Mat red(int node) {
        Mat curr;
        curr.mat[0][0] = overson[node].red;
        return curr;
    }
 
    Mat blue(int node) {
        Mat curr;
        curr.mat[1][1] = overson[node].blue;
        return curr;
    }
 
    Mat gol(int node) {
        Mat curr;
        curr.mat[0][0] = overson[node].red;
        curr.mat[1][1] = overson[node].blue;
        return curr;
    }
 
 
    void init(int n) {
        ok.mat[0][0] = 0;
        ok.mat[1][1] = 0;
        aint::init(n, ok);
//        init(0, 0);
    }
 
    int upd(int node) {
        int father = pch[node];
        aint::upd(nodepoz(node), color[node] == 0? gol(node) : color[node] == 1? red(node) : blue(node));
 
        if(father == 0) { auto R = aint::query(pin[father], lastpoz[father]); return min({R.mat[0][0],R.mat[0][1],R.mat[1][0],R.mat[1][1]});}
 
        overson[p[father]] -= mine[father];
        auto R = aint::query(pin[father], lastpoz[father]);
        mine[father] = SimpleDir(min(R.mat[0][0], R.mat[0][1]), min(R.mat[1][0], R.mat[1][1]));
        if(color[father] == 1) mine[father].blue = inf;
        if(color[father] == 2) mine[father].red = inf;
 
        overson[p[father]] += mine[father];
 
        return upd(p[node]);
    }
}
 
void initialize(int n, std::vector<int> A, std::vector<int> B) {
    for(int i = 0; i < n - 1; i++) {
        Tree::g[--A[i]].emplace_back(--B[i]);
        Tree::g[B[i]].emplace_back(A[i]);
    }
 
    Tree::Init::preinit(0, 0);
    Tree::pch[0];
    Tree::Init::init(0, 0);
 
    Tree::init(n);
 
    return;
}
 
int cat(int v) {
    Tree::color[--v] = 1;
  return Tree::upd(v);
}
 
int dog(int v) {
    Tree::color[--v] = 2;
  return Tree::upd(v);
}
 
int neighbor(int v) {
    Tree::color[--v] = 0;
  return Tree::upd(v);
}

Compilation message

catdog.cpp: In function 'void Tree::aint::upd(int, Tree::Mat, int, int, int)':
catdog.cpp:90:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |             int mid = cl + cr >> 1;
      |                       ~~~^~~~
catdog.cpp: In function 'Tree::Mat Tree::aint::query(int, int, int, int, int)':
catdog.cpp:99:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |             int mid = cl + cr >> 1;
      |                       ~~~^~~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:175:16: warning: statement has no effect [-Wunused-value]
  175 |     Tree::pch[0];
      |     ~~~~~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 3 ms 9816 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9816 KB Output is correct
14 Correct 3 ms 9816 KB Output is correct
15 Correct 3 ms 9816 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 3 ms 9816 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9816 KB Output is correct
14 Correct 3 ms 9816 KB Output is correct
15 Correct 3 ms 9816 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 10088 KB Output is correct
18 Correct 4 ms 10072 KB Output is correct
19 Correct 5 ms 10076 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 3 ms 10076 KB Output is correct
23 Correct 5 ms 10076 KB Output is correct
24 Correct 5 ms 10072 KB Output is correct
25 Correct 4 ms 10076 KB Output is correct
26 Correct 4 ms 10072 KB Output is correct
27 Correct 5 ms 10076 KB Output is correct
28 Correct 5 ms 10076 KB Output is correct
29 Correct 4 ms 10076 KB Output is correct
30 Correct 3 ms 10036 KB Output is correct
31 Correct 3 ms 10076 KB Output is correct
32 Correct 3 ms 10076 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 3 ms 9816 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9816 KB Output is correct
14 Correct 3 ms 9816 KB Output is correct
15 Correct 3 ms 9816 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 10088 KB Output is correct
18 Correct 4 ms 10072 KB Output is correct
19 Correct 5 ms 10076 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 3 ms 10076 KB Output is correct
23 Correct 5 ms 10076 KB Output is correct
24 Correct 5 ms 10072 KB Output is correct
25 Correct 4 ms 10076 KB Output is correct
26 Correct 4 ms 10072 KB Output is correct
27 Correct 5 ms 10076 KB Output is correct
28 Correct 5 ms 10076 KB Output is correct
29 Correct 4 ms 10076 KB Output is correct
30 Correct 3 ms 10036 KB Output is correct
31 Correct 3 ms 10076 KB Output is correct
32 Correct 3 ms 10076 KB Output is correct
33 Correct 1382 ms 13492 KB Output is correct
34 Correct 331 ms 13136 KB Output is correct
35 Correct 854 ms 12732 KB Output is correct
36 Correct 2592 ms 15404 KB Output is correct
37 Correct 20 ms 11356 KB Output is correct
38 Correct 2988 ms 15864 KB Output is correct
39 Correct 2731 ms 15880 KB Output is correct
40 Correct 2883 ms 15888 KB Output is correct
41 Correct 2999 ms 15880 KB Output is correct
42 Correct 2114 ms 15892 KB Output is correct
43 Correct 1887 ms 15872 KB Output is correct
44 Correct 1654 ms 15888 KB Output is correct
45 Correct 2110 ms 15904 KB Output is correct
46 Correct 2103 ms 15876 KB Output is correct
47 Correct 2442 ms 15872 KB Output is correct
48 Correct 87 ms 14332 KB Output is correct
49 Correct 94 ms 15224 KB Output is correct
50 Correct 37 ms 11308 KB Output is correct
51 Correct 39 ms 12124 KB Output is correct
52 Correct 17 ms 11100 KB Output is correct
53 Correct 991 ms 14928 KB Output is correct
54 Correct 669 ms 12392 KB Output is correct
55 Correct 1706 ms 14372 KB Output is correct
56 Correct 1243 ms 12968 KB Output is correct
57 Correct 1282 ms 14744 KB Output is correct
58 Correct 17 ms 12248 KB Output is correct
59 Correct 38 ms 12116 KB Output is correct
60 Correct 84 ms 14676 KB Output is correct
61 Correct 89 ms 14908 KB Output is correct
62 Correct 56 ms 14028 KB Output is correct
63 Execution timed out 3029 ms 15192 KB Time limit exceeded
64 Halted 0 ms 0 KB -