Submission #133832

#	Time	Username	Problem	Language	Result	Execution time	Memory
133832		osaaateiasavtnl	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	4 ms	2680 KiB

catdog

#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
const int N = 1e5 + 7;
vector <int> g[N];
void initialize(int n, vector <int> a, vector <int> b) {
    for (int i = 0; i < n - 1; ++i) {
        g[a[i]].app(b[i]);
        g[b[i]].app(a[i]);
    }   
    g[0].app(1);
}   
int type[N];
int ans = 0;
int cnt[2];
void dfs(int u, int p, int part) {
    if (type[u] == -1) {
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u, part);
            }   
        }   
    }   
    else {
        if (part == -1) {
            ++cnt[type[u]];    
        }   
        else {
            ans += type[u] ^ part;
        }   
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u, type[u]);
            }   
        }   
    }   
}   
int f() {
    ans = cnt[0] = cnt[1] = 0;
    dfs(0, 0, -1);
    return ans + min(cnt[0], cnt[1]);
}   
int cat(int u) {
    type[u] = 0;
    return f();
}
int dog(int u) {
    type[u] = 1;
    return f();
}
int neighbor(int u) {
    type[u] = -1;
    return f();        
}   
#ifdef HOME
signed main() {
    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    vector <int> a, b;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        a.app(u); b.app(v);
    }   
    initialize(n, a, b);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int t, u;
        cin >> t >> u;
        if (t == 1) cout << cat(u) << '\n';
        else if (t == 2) cout << dog(u) << '\n';
        else cout << neighbor(u) << '\n';
    }   
}       
#endif

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