oj.uz

Submission #443140

# Submission time Handle Problem Language Result Execution time Memory
443140 2021-07-09T19:25:56 Z blue Mergers (JOI19_mergers) C++17
0 / 100
 84 ms 37008 KB 
#include <iostream>
#include <set>
#include <vector>
using namespace std;

const int maxN = 500'000;

vector<int> edge[1+maxN];
vector<int> parent(1+maxN, 0);
vector<int> subtree(1+maxN, 1);
vector<int> max_child(1+maxN, -1);

void dfs1(int u)
{
    for(int v: edge[u])
    {
        if(parent[u] == v) continue;
        parent[v] = u;
        dfs1(v);
        subtree[u] += subtree[v];
        if(max_child[u] == -1 || subtree[v] > subtree[ max_child[u] ])
            max_child[u] = v;
    }
}




struct state
{
    int i;
    int c;
};

bool operator < (state A, state B)
{
    return A.i < B.i;
}

int S[1+maxN];
vector<int> state_count(1+maxN, 0);

set<state>* T[1+maxN];



void add_state(int u, state x)
{
    // cerr << "add_state " << u << ' ' << x.i << ' ' << x.c << '\n';
    set<state>::iterator it = T[u]->find(x);
    if(it == T[u]->end())
    {
        // cerr << "case A\n";
        if(x.c != state_count[x.i])
            T[u]->insert(x);
    }
    else
    {
        // cerr << "case B\n";
        int ct = it->c + x.c;
        T[u]->erase(it);
        if(ct != state_count[x.i])
        {
            T[u]->insert(state{x.i, ct});
        }
    }
}

int bad_edge_count = 0;

bool dfs2(int u) //returns if we have found any bad edges yet.
{
    // cerr << "dfs2 " << u << ' ' << max_child[u] << '\n';
    bool flag = 0;
    if(max_child[u] == -1)
    {
        // cerr << "case 1\n";
        T[u] = new set<state>;
        add_state(u, state{S[u], 1});
    }
    else
    {
        for(int v: edge[u])
        {
            if(v == parent[u]) continue;
            // cerr << u << " -> " << v << '\n';
            flag |= dfs2(v);
        }

        // cerr << "case 2\n";
        T[u] = T[ max_child[u] ];
        // cerr << "x\n";
        add_state(u, state{S[u], 1});
        // cerr << "check X\n";
        for(int v: edge[u])
        {
            // cerr << "v = " << v << '\n';
            if(v == parent[u] || v == max_child[u]) continue;

            for(state s: *(T[v]))
                add_state(u, s);

            T[v]->clear();
        }
    }

    if(T[u]->size() == 0 && u != 1)
    {
        if(!flag)
        {
            // cerr << "adding bad edge at " << u << '\n';
            bad_edge_count++;
        }
        return 1;
    }
    else
    {
        return flag;
    }

}






int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;

    for(int i = 1; i <= N-1; i++)
    {
        int A, B;
        cin >> A >> B;
        edge[A].push_back(B);
        edge[B].push_back(A);
    }

    for(int i = 1; i <= N; i++)
    {
        cin >> S[i];
        state_count[ S[i] ]++;
    }

    // cerr << "check 0\n";

    parent[1] = 1;
    dfs1(1);

    // cerr << "check 1\n";

    dfs2(1);

    // cerr << "check 2\n";

    int res = (bad_edge_count / 2) + (bad_edge_count % 2);

    cout << res << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19916 KB Output is correct
2 Correct 12 ms 19916 KB Output is correct
3 Correct 12 ms 19924 KB Output is correct
4 Correct 12 ms 19916 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 12 ms 19916 KB Output is correct
7 Correct 11 ms 19916 KB Output is correct
8 Correct 13 ms 19840 KB Output is correct
9 Correct 11 ms 19916 KB Output is correct
10 Correct 11 ms 19916 KB Output is correct
11 Correct 12 ms 19924 KB Output is correct
12 Correct 12 ms 19820 KB Output is correct
13 Correct 12 ms 19916 KB Output is correct
14 Correct 11 ms 19884 KB Output is correct
15 Correct 12 ms 19916 KB Output is correct
16 Incorrect 12 ms 19924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19916 KB Output is correct
2 Correct 12 ms 19916 KB Output is correct
3 Correct 12 ms 19924 KB Output is correct
4 Correct 12 ms 19916 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 12 ms 19916 KB Output is correct
7 Correct 11 ms 19916 KB Output is correct
8 Correct 13 ms 19840 KB Output is correct
9 Correct 11 ms 19916 KB Output is correct
10 Correct 11 ms 19916 KB Output is correct
11 Correct 12 ms 19924 KB Output is correct
12 Correct 12 ms 19820 KB Output is correct
13 Correct 12 ms 19916 KB Output is correct
14 Correct 11 ms 19884 KB Output is correct
15 Correct 12 ms 19916 KB Output is correct
16 Incorrect 12 ms 19924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19916 KB Output is correct
2 Correct 12 ms 19916 KB Output is correct
3 Correct 12 ms 19924 KB Output is correct
4 Correct 12 ms 19916 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 12 ms 19916 KB Output is correct
7 Correct 11 ms 19916 KB Output is correct
8 Correct 13 ms 19840 KB Output is correct
9 Correct 11 ms 19916 KB Output is correct
10 Correct 11 ms 19916 KB Output is correct
11 Correct 12 ms 19924 KB Output is correct
12 Correct 12 ms 19820 KB Output is correct
13 Correct 12 ms 19916 KB Output is correct
14 Correct 11 ms 19884 KB Output is correct
15 Correct 12 ms 19916 KB Output is correct
16 Incorrect 12 ms 19924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 37008 KB Output is correct
2 Incorrect 70 ms 32512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19916 KB Output is correct
2 Correct 12 ms 19916 KB Output is correct
3 Correct 12 ms 19924 KB Output is correct
4 Correct 12 ms 19916 KB Output is correct
5 Correct 12 ms 19924 KB Output is correct
6 Correct 12 ms 19916 KB Output is correct
7 Correct 11 ms 19916 KB Output is correct
8 Correct 13 ms 19840 KB Output is correct
9 Correct 11 ms 19916 KB Output is correct
10 Correct 11 ms 19916 KB Output is correct
11 Correct 12 ms 19924 KB Output is correct
12 Correct 12 ms 19820 KB Output is correct
13 Correct 12 ms 19916 KB Output is correct
14 Correct 11 ms 19884 KB Output is correct
15 Correct 12 ms 19916 KB Output is correct
16 Incorrect 12 ms 19924 KB Output isn't correct
17 Halted 0 ms 0 KB -