oj.uz

Submission #923559

# Submission time Handle Problem Language Result Execution time Memory
923559 2024-02-07T12:17:08 Z danikoynov Mergers (JOI19_mergers) C++14
34 / 100
 9 ms 1628 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 = 0; i < group[d].size(); i ++)
        {
            int bef = i - 1;
            if (bef < 0)
                bef = group[d].size() - 1;
            mark_path(group[d][bef], 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)
{
    ///cout << v << " : " << p << endl;
    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 << 0 << 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;
}

/**
10 5
1 3
9 6
8 6
3 10
3 2
1 6
8 7
2 5
9 4
1
1
3
2
2
5
3
1
4
2

*/

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 = 0; i < group[d].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 856 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 856 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 1624 KB Output is correct
27 Correct 3 ms 1628 KB Output is correct
28 Correct 3 ms 1624 KB Output is correct
29 Correct 3 ms 1256 KB Output is correct
30 Correct 3 ms 1336 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 3 ms 1372 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 3 ms 1368 KB Output is correct
35 Correct 3 ms 1372 KB Output is correct
36 Correct 3 ms 1372 KB Output is correct
37 Correct 3 ms 1372 KB Output is correct
38 Correct 0 ms 604 KB Output is correct
39 Correct 3 ms 1372 KB Output is correct
40 Correct 3 ms 1252 KB Output is correct
41 Correct 3 ms 1372 KB Output is correct
42 Correct 3 ms 1372 KB Output is correct
43 Correct 9 ms 1372 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 3 ms 1372 KB Output is correct
46 Correct 3 ms 1372 KB Output is correct
47 Correct 0 ms 604 KB Output is correct
48 Correct 4 ms 1372 KB Output is correct
49 Correct 3 ms 1368 KB Output is correct
50 Correct 3 ms 1368 KB Output is correct
51 Correct 3 ms 1372 KB Output is correct
52 Correct 2 ms 1372 KB Output is correct
53 Correct 3 ms 1368 KB Output is correct
54 Correct 3 ms 1372 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 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 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 856 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 0 ms 604 KB Output is correct
26 Runtime error 1 ms 1116 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1368 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 600 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 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 856 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 1624 KB Output is correct
27 Correct 3 ms 1628 KB Output is correct
28 Correct 3 ms 1624 KB Output is correct
29 Correct 3 ms 1256 KB Output is correct
30 Correct 3 ms 1336 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 3 ms 1372 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 3 ms 1368 KB Output is correct
35 Correct 3 ms 1372 KB Output is correct
36 Correct 3 ms 1372 KB Output is correct
37 Correct 3 ms 1372 KB Output is correct
38 Correct 0 ms 604 KB Output is correct
39 Correct 3 ms 1372 KB Output is correct
40 Correct 3 ms 1252 KB Output is correct
41 Correct 3 ms 1372 KB Output is correct
42 Correct 3 ms 1372 KB Output is correct
43 Correct 9 ms 1372 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 3 ms 1372 KB Output is correct
46 Correct 3 ms 1372 KB Output is correct
47 Correct 0 ms 604 KB Output is correct
48 Correct 4 ms 1372 KB Output is correct
49 Correct 3 ms 1368 KB Output is correct
50 Correct 3 ms 1368 KB Output is correct
51 Correct 3 ms 1372 KB Output is correct
52 Correct 2 ms 1372 KB Output is correct
53 Correct 3 ms 1368 KB Output is correct
54 Correct 3 ms 1372 KB Output is correct
55 Correct 0 ms 604 KB Output is correct
56 Runtime error 1 ms 1116 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -