oj.uz

Submission #445695

# Submission time Handle Problem Language Result Execution time Memory
445695 2021-07-19T09:42:32 Z blue Mergers (JOI19_mergers) C++17
0 / 100
 100 ms 39480 KB 
#include <iostream>
#include <set>
#include <vector>
#include <cstdlib>
#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++);
  rt = 1 + rand()%N;
 
    parent[rt] = rt;
    dfs1(rt);
 
    // cerr << "check 1\n";
 
    dfs2(rt);
 
    int res = (1 + bad_count[rt])/2;
 
    cout << res << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23768 KB Output is correct
4 Correct 15 ms 23736 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23848 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 15 ms 23836 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 18 ms 23792 KB Output is correct
11 Correct 15 ms 23820 KB Output is correct
12 Correct 15 ms 23744 KB Output is correct
13 Correct 15 ms 23796 KB Output is correct
14 Correct 15 ms 23732 KB Output is correct
15 Correct 18 ms 23756 KB Output is correct
16 Incorrect 15 ms 23756 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23768 KB Output is correct
4 Correct 15 ms 23736 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23848 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 15 ms 23836 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 18 ms 23792 KB Output is correct
11 Correct 15 ms 23820 KB Output is correct
12 Correct 15 ms 23744 KB Output is correct
13 Correct 15 ms 23796 KB Output is correct
14 Correct 15 ms 23732 KB Output is correct
15 Correct 18 ms 23756 KB Output is correct
16 Incorrect 15 ms 23756 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23768 KB Output is correct
4 Correct 15 ms 23736 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23848 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 15 ms 23836 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 18 ms 23792 KB Output is correct
11 Correct 15 ms 23820 KB Output is correct
12 Correct 15 ms 23744 KB Output is correct
13 Correct 15 ms 23796 KB Output is correct
14 Correct 15 ms 23732 KB Output is correct
15 Correct 18 ms 23756 KB Output is correct
16 Incorrect 15 ms 23756 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23768 KB Output is correct
4 Correct 15 ms 23736 KB Output is correct
5 Correct 15 ms 23788 KB Output is correct
6 Correct 15 ms 23848 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 15 ms 23836 KB Output is correct
9 Correct 15 ms 23756 KB Output is correct
10 Correct 18 ms 23792 KB Output is correct
11 Correct 15 ms 23820 KB Output is correct
12 Correct 15 ms 23744 KB Output is correct
13 Correct 15 ms 23796 KB Output is correct
14 Correct 15 ms 23732 KB Output is correct
15 Correct 18 ms 23756 KB Output is correct
16 Incorrect 15 ms 23756 KB Output isn't correct
17 Halted 0 ms 0 KB -