oj.uz

Submission #445305

# Submission time Handle Problem Language Result Execution time Memory
445305 2021-07-17T11:35:12 Z blue Mergers (JOI19_mergers) C++17
0 / 100
 207 ms 44504 KB 
#include <iostream>
#include <set>
#include <vector>
#include <queue>
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;

struct edg
{
    int u;
    int v;

    edg(int U, int V)
    {
        u = min(U, V);
        v = max(U, V);
    }
};

bool operator < (edg A, edg B)
{
    if(A.u == B.u) return A.v < B.v;
    return A.u < B.u;
}

set<edg> bad_edges;

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;
        bad_edges.insert(edg(u, parent[u]));
    }

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

    // res = (1 + bad_count[rt])/2;

    int res = 0;
    queue<int> tbv;

    vector<int> visit(1+N, 0);

    for(int i = 1; i <= N; i++)
        if(edge[i].size() == 1)
        {
            tbv.push(i);
            visit[i] = 1;
        }

    set<edg> ans_set;

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        for(int v: edge[u])
        {
            if(visit[v]) continue;
            if(bad_edges.find(edg(u, v)) == bad_edges.end())
            {
                visit[v] = 1;
                tbv.push(v);
            }
            else
            {
                ans_set.insert(edg(u, v));
            }
        }
    }

    int ct = ans_set.size();

    res = (1+ct)/2;

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Incorrect 15 ms 23756 KB Output isn't correct
3 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 Incorrect 15 ms 23756 KB Output isn't correct
3 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 Incorrect 15 ms 23756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 40244 KB Output is correct
2 Correct 207 ms 44504 KB Output is correct
3 Incorrect 18 ms 24100 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 Incorrect 15 ms 23756 KB Output isn't correct
3 Halted 0 ms 0 KB -