oj.uz

Submission #376724

# Submission time Handle Problem Language Result Execution time Memory
376724 2021-03-12T02:43:04 Z 2qbingxuan Mergers (JOI19_mergers) C++14
0 / 100
 69 ms 20584 KB 
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : "\033[0m)\n")));
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
const int64_t INF = 1e18;
const int maxn = 500025;

struct Dsu {
    int pa[maxn], rk[maxn];
    int anc(int x) { return x==pa[x] ? x : pa[x] = anc(pa[x]); }
    void init(int n) {
        for (int i = 1; i <= n; i++)
            pa[i] = i, rk[i] = 0;
    }
    bool join(int x, int y) {
        if ((x=anc(x)) == (y=anc(y))) return false;
        if (rk[x] < rk[y]) swap(x, y);
        return pa[y] = x, rk[x]!=rk[y] || ++rk[x];
    }
} dsu;

vector<int> g[maxn];
vector<pair<int,int>> ed;
int s[maxn];
int cnt[2][maxn], has;
void dfs(int i, int p = 0) {
    if (has > 0) {
        dsu.join(i, p);
    } else if (p) {
        ed.emplace_back(i, p);
    }
    has -= (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    cnt[0][s[i]] -= 1;
    cnt[1][s[i]] += 1;
    has += (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    for (int j: g[i]) {
        if (j != p) {
            dfs(j, i);
        }
    }
    has -= (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
    cnt[0][s[i]] += 1;
    cnt[1][s[i]] -= 1;
    has += (min(cnt[0][s[i]], cnt[1][s[i]]) > 0);
}
bool vis[maxn];
int leaf = 0;
void dfs2(int i) {
    debug(i);
    if (g[i].size() == 1) ++leaf;
    vis[i] = true;
    for (int j: g[i]) {
        if (!vis[j])
            dfs2(j);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) ++cnt[0][s[i]];
    dsu.init(n);
    dfs(1);
    for (int i = 1; i <= n; i++) g[i].clear();
    for (auto [a, b]: ed) {
        a = dsu.anc(a);
        b = dsu.anc(b);
        g[a].emplace_back(b);
        g[b].emplace_back(a);
        debug(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        leaf = 0;
        dfs2(i);
        debug(leaf);
        ans += (leaf + 1) / 2;
    }
    cout << ans << '\n';
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for (auto [a, b]: ed) {
      |               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16868 KB Output is correct
2 Correct 69 ms 20584 KB Output is correct
3 Incorrect 11 ms 12268 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct
2 Halted 0 ms 0 KB -