oj.uz

Submission #445151

# Submission time Handle Problem Language Result Execution time Memory
445151 2021-07-16T16:20:42 Z blue Mergers (JOI19_mergers) C++17
0 / 100
 125 ms 41148 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 = 1;

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);

    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 23756 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23840 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 15 ms 23832 KB Output is correct
6 Correct 15 ms 23776 KB Output is correct
7 Correct 15 ms 23836 KB Output is correct
8 Correct 15 ms 23820 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 15 ms 23824 KB Output is correct
12 Incorrect 16 ms 23812 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 23756 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23840 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 15 ms 23832 KB Output is correct
6 Correct 15 ms 23776 KB Output is correct
7 Correct 15 ms 23836 KB Output is correct
8 Correct 15 ms 23820 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 15 ms 23824 KB Output is correct
12 Incorrect 16 ms 23812 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 23756 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23840 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 15 ms 23832 KB Output is correct
6 Correct 15 ms 23776 KB Output is correct
7 Correct 15 ms 23836 KB Output is correct
8 Correct 15 ms 23820 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 15 ms 23824 KB Output is correct
12 Incorrect 16 ms 23812 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 40864 KB Output is correct
2 Correct 125 ms 41148 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 23756 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 15 ms 23840 KB Output is correct
4 Correct 15 ms 23812 KB Output is correct
5 Correct 15 ms 23832 KB Output is correct
6 Correct 15 ms 23776 KB Output is correct
7 Correct 15 ms 23836 KB Output is correct
8 Correct 15 ms 23820 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 15 ms 23824 KB Output is correct
12 Incorrect 16 ms 23812 KB Output isn't correct
13 Halted 0 ms 0 KB -