Submission #133832

# Submission time Handle Problem Language Result Execution time Memory
133832 2019-07-21T13:42:34 Z osaaateiasavtnl Cats or Dogs (JOI18_catdog) C++14
0 / 100
4 ms 2680 KB
#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
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -