oj.uz

Submission #445154

# Submission time Handle Problem Language Result Execution time Memory
445154 2021-07-16T16:28:54 Z blue Mergers (JOI19_mergers) C++17
0 / 100
 122 ms 39484 KB 
#include <iostream>
#include <set>
#include <vector>
#include <set>
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);

int rt = 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});
        }
    }
}

vector<int> is_bad(1+maxN, 0);

vector<int> bad_count(1+maxN, 0);

int meeting_point = 0;

void dfs2(int u)
{
    // cerr << "dfs2 " << u << ' ' << max_child[u] << '\n';
    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;
            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();
        }
    }

    int lower_bad_count = 0;;
    for(int v: edge[u])
    {
        if(v == parent[u]) continue;
        lower_bad_count += bad_count[v];
    }

    if(T[u]->size() == 0 && u != rt)
    {
        is_bad[u] = 1;
    }

    if(lower_bad_count)
    {
        bad_count[u] = lower_bad_count;
    }
    else if(is_bad[u])
    {
        bad_count[u] = 1;
    }
    else
    {
        bad_count[u] = 0;
    }

    if(bad_count[u] > bad_count[meeting_point]) meeting_point = u;
    else if(bad_count[u] == bad_count[meeting_point] && subtree[u] < subtree[meeting_point])
        meeting_point = u;
}






int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    bad_count[0] = -1;
    subtree[0] = 1e9;

    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] ]++;
    }

    if(N == 2)
    {
        cout << "1\n";
        return 0;
    }

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

    for(rt = 1; edge[rt].size() == 1; rt++);

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

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

    dfs2(rt);

    if(is_bad[meeting_point])
        meeting_point = parent[meeting_point];

    multiset<int> X;
    for(int v: edge[meeting_point])
        if(v != parent[meeting_point])
        {
            X.insert(bad_count[v]);
        }

    int res = 0;
    while(1)
    {
        X.erase(0);
        if(X.size() == 0) break;
        else if(X.size() == 1)
        {
            res += *X.begin();
            break;
        }
        else
        {
            multiset<int>::iterator p1 = X.end();
            p1--;

            multiset<int>::iterator p2 = X.end();
            p2--;
            p2--;

            int P1 = *p1;
            int P2 = *p2;

            X.erase(X.find(P1));
            X.erase(X.find(P2));
            res++;

            P1--;
            P2--;
            X.insert(P1);
            X.insert(P2);
        }
    }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 15 ms 23744 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 14 ms 23776 KB Output is correct
10 Correct 15 ms 23792 KB Output is correct
11 Correct 15 ms 23724 KB Output is correct
12 Incorrect 17 ms 23800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 15 ms 23744 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 14 ms 23776 KB Output is correct
10 Correct 15 ms 23792 KB Output is correct
11 Correct 15 ms 23724 KB Output is correct
12 Incorrect 17 ms 23800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 15 ms 23744 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 14 ms 23776 KB Output is correct
10 Correct 15 ms 23792 KB Output is correct
11 Correct 15 ms 23724 KB Output is correct
12 Incorrect 17 ms 23800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 39388 KB Output is correct
2 Correct 122 ms 39484 KB Output is correct
3 Incorrect 17 ms 24012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23724 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 15 ms 23744 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 14 ms 23776 KB Output is correct
10 Correct 15 ms 23792 KB Output is correct
11 Correct 15 ms 23724 KB Output is correct
12 Incorrect 17 ms 23800 KB Output isn't correct
13 Halted 0 ms 0 KB -