제출 #134047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134047		osaaateiasavtnl	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1113 ms	26012 KiB

catdog

#include<bits/stdc++.h>
using namespace std;
#define app push_back
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
struct Dp {
    int a[2][2];
    Dp () {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                a[i][j] = INF;
            }   
        }   
    }   
    int* operator[](int i) {
        return a[i];
    }   
    Dp operator *(Dp add) {
        Dp ans;        
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int ii = 0; ii < 2; ++ii) {
                    for (int jj = 0; jj < 2; ++jj) {
                        ans[i][jj] = min(ans[i][jj], a[i][j] + add[ii][jj] + (j ^ ii));    
                    }   
                }   
            }   
        }   
        return ans;
    }   
};  
int cnt[N], to[N];
vector <int> g[N];
void dfs1(int u, int p) {
    cnt[u] = 1;
    int mx = -1;
    for (int v : g[u]) {
        if (v != p) {
            dfs1(v, u);
            cnt[u] += cnt[v];
            if (mx == -1 || cnt[mx] < cnt[v]) mx = v;
        }   
    }
    if (mx == -1) {
        to[u] = u;
        return;
    }
    int pos = -1;
    for (int i = 0; i < g[u].size(); ++i) {
        if (g[u][i] == mx) pos = i;
    }   
    swap(g[u][0], g[u][pos]);    
    to[u] = to[mx];
}   
int up[N], pos[N], par[N], ptr = 0;
void dfs2(int u, int p) {
    par[u] = p; pos[u] = ptr++;
    for (int v : g[u]) {
        if (v != p) {
            if (v == g[u][0]) up[v] = up[u];
            else up[v] = v;
            dfs2(v, u);
        }   
    }
}
Dp tree[N << 2];
Dp EM;
Dp get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return EM;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) >> 1;
    return get(v * 2 + 1, tl, tm, l, r) * get(v * 2 + 2, tm + 1, tr, l, r);
}   
void relax(int v) {
    tree[v] = tree[v * 2 + 1] * tree[v * 2 + 2];
}
void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = EM;
        return;
    }   
    int tm = (tl + tr) >> 1;
    build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
    relax(v);
}     
void upd(int v, int tl, int tr, int p, int d0, int d1) {
    if (tl == tr) {
        tree[v][0][0] += d0; tree[v][1][1] += d1;
        return;
    }   
    int tm = (tl + tr) >> 1;
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, d0, d1);
    else upd(v * 2 + 2, tm + 1, tr, p, d0, d1);
    relax(v);
}   
void initialize(int n, vector <int> a, vector <int> b) {
    EM[0][0] = EM[1][1] = 0;
    for (int i = 0; i < n - 1; ++i) {
        g[a[i]].app(b[i]); g[b[i]].app(a[i]);
    }       
    up[1] = 1;
    dfs1(1, 0); 
    dfs2(1, 0);
    build(0, 0, N);
}
pair <int, int> get_dp(int v) {
    auto m = get(0, 0, N, pos[v], pos[to[v]]);
    int dp0 = min(m[0][0], m[0][1]), dp1 = min(m[1][0], m[1][1]);
    return {min(dp0, dp1 + 1), min(dp0 + 1, dp1)};
}   
int get() {
    auto m = get(0, 0, N, pos[1], pos[to[1]]);
    int dp0 = min(m[0][0], m[0][1]), dp1 = min(m[1][0], m[1][1]);
    return min(dp0, dp1);
}
void anime(int v, int d0, int d1) {
    while (v) {
        int f0, f1, s0, s1;
        tie(f0, f1) = get_dp(up[v]);
        upd(0, 0, N, pos[v], d0, d1);
        tie(s0, s1) = get_dp(up[v]);
        d0 = s0 - f0; d1 = s1 - f1;
        v = par[up[v]];
    }   
}   
bool type[N];   
int cat(int v) {
    type[v] = 0; anime(v, 0, INF); return get();
}
int dog(int v) {
    type[v] = 1; anime(v, INF, 0); return get();
}
int neighbor(int v) {
    if (type[v]) anime(v, -INF, 0);
    else anime(v, 0, -INF);
    return get();
}   
#ifdef HOME
signed main() {
    freopen("input.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    vector <int> a, b;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        a.push_back(u); b.push_back(v);
    }   
    initialize(n, a, b);
    for (int i = 0; i < q; ++i) {
        int t, v;
        cin >> t >> v;
        if (t == 1) cout << cat(v) << '\n';
        else if (t == 2) cout << dog(v) << '\n';
        else cout << neighbor(v) << '\n';
    }   
}   
#endif
/*
5 3
1 2
1 4
2 3
2 4
1 3
2 5
2 4
*/

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp: In function 'void dfs1(int, int)':
catdog.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[u].size(); ++i) {
                     ~~^~~~~~~~~~~~~

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