oj.uz

Submission #923550

# Submission time Handle Problem Language Result Execution time Memory
923550 2024-02-07T12:09:30 Z danikoynov Mergers (JOI19_mergers) C++14
0 / 100
 1 ms 1112 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 3010;
int n, k, state[maxn];
vector < int > adj[maxn], group[maxn];
void input()
{
    cin >> n >> k;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i ++)
    {
        cin >> state[i];
        group[state[i]].push_back(i);
    }
}

int tin[maxn], tout[maxn], timer;
int occ[2 * maxn], depth[maxn], par[maxn];
void dfs(int v, int p)
{
    tin[v] = ++ timer;
    occ[timer] = v;
    par[v] = p;
    for (int u : adj[v])
    {
        if (u == p)
            continue;

        depth[u] = depth[v] + 1;
        dfs(u, v);
        occ[++ timer] = v;
    }

    tout[v] = timer;
}

const int maxlog = 22;

int dp[maxlog][maxn * 2], lg[maxn * 2];
void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
    {
        dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
        if (depth[dp[j - 1][i]] < depth[dp[j][i]])
            dp[j][i] = dp[j - 1][i];
    }
}

int get_lca(int v, int u)
{
    v = tin[v];
    u = tin[u];
    if (v > u)
        swap(v, u);
    int len = lg[u - v + 1] - 1;
    int res = dp[len][u - (1 << len) + 1];
    if (depth[dp[len][v]] < depth[res])
        res = dp[len][v];

    return res;
}

int mark[maxn];
void mark_path(int v, int u)
{
    int lca = get_lca(v, u);
    while(v != lca)
    {
        mark[v] = 1;
        v = par[v];
    }
    while(u != lca)
    {
        mark[u] = 1;
        u = par[u];
    }
}

void find_redundant()
{
    for (int d = 1; d <= k; d ++)
    {
        for (int i = 1; i < group[d].size(); i ++)
        {
            mark_path(group[d][i - 1], group[d][i]);
        }
    }
}

vector < int > g[maxn];
int used[maxn];
int cp_cnt;

void trav(int v)
{
    used[v] = cp_cnt;
    for (int u : g[v])
    {
        if (used[u] != 0)
            continue;
        trav(u);
    }
}

vector < int > bridge[maxn];
void build_new_graph()
{
    /// exclude 1
    for (int i = 2; i <= n; i ++)
    {
        if (mark[i])
        {
            g[i].push_back(par[i]);
            g[par[i]].push_back(i);
        }
    }

    //for (int i = 1; i <= n; i ++)
      //  cout << "mark " << i << " " << mark[i] << endl;
    for (int i = 1; i <= n; i ++)
    {
        if (!used[i])
        {
            cp_cnt ++;
            trav(i);
        }
    }

    //for (int i = 1; i <= n; i ++)
     //   cout << i << " " << used[i] << endl;

    for (int i = 2; i <= n; i ++)
    {
        if (!mark[i])
        {
            assert(used[par[i]] != used[i]);
            bridge[used[i]].push_back(used[par[i]]);
            bridge[used[par[i]]].push_back(used[i]);
        }
    }
}

int find_leaves(int v, int p)
{
    int child = 0, leaves = 0;
    used[v] = 1;
    for (int u : bridge[v])
    {
        if (used[u] == 1)
            continue;
        child ++;
        leaves += find_leaves(u, v);
    }
    if ((p == -1 && child < 2) || child == 0)
        leaves ++;
    return leaves;
}

void print()
{
    memset(used, 0, sizeof(used));
    int res = find_leaves(1, - 1);
    if (res == 1)
        cout << 1 << endl;
    else
        cout << (res + 1) / 2 << endl;
}
void solve()
{
    input();
    dfs(1, -1);
    build_sparse_table();
    find_redundant();
    build_new_graph();
    print();

}

int main()
{
    solve();
    return 0;
}

Compilation message

mergers.cpp: In function 'void find_redundant()':
mergers.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 1; i < group[d].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -