oj.uz

Submission #421820

# Submission time Handle Problem Language Result Execution time Memory
421820 2021-06-09T12:37:45 Z 반딧불(#7622) Cats or Dogs (JOI18_catdog) C++17
0 / 100
 28 ms 47308 KB 
#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll LIM = 1e18;

struct Matrix{
    ll mat[3][3];
    Matrix(){
        for(int i=0; i<9; i++) mat[i/3][i%3] = 0;
    }
    Matrix(vector<ll> vec){
        for(int i=0; i<9; i++) mat[i/3][i%3] = vec[i];
    }

    Matrix operator+(const vector<ll> &r)const{
        Matrix ret;
        for(int i=0; i<3; i++) for(int j=0; j<3; j++) ret.mat[i][j] = mat[i][j] + r[j];
        return ret;
    }

    Matrix operator*(const Matrix &r)const{
        Matrix ret;
        for(int a=0; a<3; a++){
            for(int b=0; b<3; b++){
                ret.mat[a][b] = LIM;
                for(int c=0; c<3; c++){
                    ret.mat[a][b] = min(ret.mat[a][b], mat[a][c] + r.mat[c][b]);
                }
            }
        }
        return ret;
    }

    vector<ll> render()const{
        vector<ll> ret (3, LIM);
        for(int i=0; i<3; i++) for(int j=0; j<3; j++) ret[j] = min(ret[j], mat[i][j]);
        return ret;
    }
};

struct segTree{
    Matrix tree[400002];
    segTree(){}

    void update(int i, int l, int r, int x, Matrix &val){
        if(l==r){
            for(int j=0; j<3; j++) for(int k=0; k<3; k++) tree[i] = val;
            return;
        }
        int m = (l+r)>>1;
        if(x <= m) update(i*2, l, m, x, val);
        else update(i*2+1, m+1, r, x, val);
        tree[i] = tree[i*2] * tree[i*2+1];
    }

    Matrix query(int i, int l, int r, int s, int e){
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        if(e<=m) return query(i*2, l, m, s, e);
        if(m<s) return query(i*2+1, m+1, r, s, e);
        return query(i*2, l, m, s, e) * query(i*2+1, m+1, r, s, e);
    }
} tree;

int n;
int x;
int arr[100002];
vector<int> link[100002];
ll DP[100002][3];

int in[100002], top[100002], idx[100002], sz[100002], depth[100002], par[100002], tail[100002], inCnt;
void dfs_sz(int x, int p=-1){
    if(p!=-1) link[x].erase(find(link[x].begin(), link[x].end(), p));
    sz[x] = 1;
    for(auto &y: link[x]){
        depth[y] = depth[x] + 1;
        par[y] = x;
        dfs_sz(y, x);
        sz[x] += sz[y];
        if(sz[y] > sz[link[x][0]]) swap(y, link[x][0]);
    }
}

void dfs_hld(int x){
    in[x] = ++inCnt;
    idx[in[x]] = x;
    for(auto y: link[x]){
        top[y] = y == link[x][0] ? top[x] : y;
        dfs_hld(y);
    }
}

Matrix cost[100002];
Matrix sum[100002];
vector<ll> slack[100002];
const Matrix preset[3] = {
    Matrix ({0, 0, 0, 1, 0, 1, 1, 1, 0}),
    Matrix ({LIM, 0, LIM, LIM, 0, LIM, LIM, 1, LIM}),
    Matrix ({LIM, LIM, 0, LIM, LIM, 1, LIM, LIM, 0})
};

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    for(int i=0; i<n-1; i++){
        link[A[i]].push_back(B[i]);
        link[B[i]].push_back(A[i]);
    }
    dfs_sz(1);
    top[1] = 1;
    dfs_hld(1);

    for(int i=1; i<=n; i++){
        cost[i] = sum[i] = preset[0];
        tree.update(1, 1, n, in[i], cost[i]);
        slack[i].resize(3);

        if(in[i] > in[tail[top[i]]]) tail[top[i]] = i;
    }
}

int change(int, int);
int cat(int v){
    return change(v, 1);
}
int dog(int v) {
    return change(v, 2);
}
int neighbor(int v){
    return change(v, 3);
}

vector<ll> upgrade(vector<ll> vec){
    vector<ll> ret {min({vec[0], vec[1]+1, vec[2]+1}), min({vec[0], vec[1], vec[2]+1}), min({vec[0], vec[1]+1, vec[2]})};
    return ret;
}

int change(int v, int to){
    cost[v] = preset[to];

    vector<ll> vec;
    int x = v;
    while(x){
        int p = par[top[x]];
        int s = in[top[x]];
        int e = in[tail[top[x]]];
        vec = upgrade(tree.query(1, 1, n, s, e).render());
        if(p) for(int j=0; j<3; j++) slack[p][j] -= vec[j];

        sum[x] = cost[x] + slack[x];
        tree.update(1, 1, n, in[x], sum[x]);
        vec = upgrade(tree.query(1, 1, n, s, e).render());
        if(p) for(int j=0; j<3; j++) slack[p][j] += vec[j];

        x = p;
    }

    int s2 = 1, e2 = in[tail[1]];
    vector<ll> tmp = upgrade(tree.query(1, 1, n, s2, e2).render());
    return *min_element(tmp.begin(), tmp.end());
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47308 KB Output is correct
2 Incorrect 27 ms 47272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47308 KB Output is correct
2 Incorrect 27 ms 47272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47308 KB Output is correct
2 Incorrect 27 ms 47272 KB Output isn't correct
3 Halted 0 ms 0 KB -