oj.uz

Submission #941170

# Submission time Handle Problem Language Result Execution time Memory
941170 2024-03-08T08:49:15 Z vjudge1 Mergers (JOI19_mergers) C++17
0 / 100
 186 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 5e5+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,k, s[SZ], h[SZ], up[SZ][20], sum[SZ];
vector<int> adj[SZ], adj2[SZ], vec[SZ];
vector<pii> edges;

struct DSU
{
    int par[SZ], s[SZ];

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            par[i] = i;
            s[i] = 1;
        }
    }

    int get(int u)
    {
        return (par[u] == u ? u : par[u] = get(par[u]));
    }

    void join(int u, int v)
    {
        u = get(u);
        v = get(v);
        if(u == v) return;
        if(s[u] < s[v]) swap(u,v);
        par[v] = u;
        s[u] += s[v];
    }

    bool joined(int u, int v)
    {
        u = get(u);
        v = get(v);
        return u == v;
    }
} dsu;

void dfs1(int u, int pre)
{
    for(int v : adj[u])
    {
        if(v == pre) continue;
        up[v][0] = u;
        for(int i = 1; i < 20; i++)
        {
            up[v][i] = up[up[v][i-1]][i-1];
        }
        h[v] = h[u] + 1;
        dfs1(v, u);
    }
}

int lca(int u, int v)
{
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u,v);
        int dif = h[u] - h[v];
        for(int i = 0; i < 20; i++)
        {
            if(dif >> i & 1) u = up[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--)
    {
        if(up[u][i] == up[v][i]) continue;
        u = up[u][i];
        v = up[v][i];
    }
    return up[u][0];
}

void dfs2(int u, int pre)
{
    for(int v : adj[u])
    {
        if(v == pre) continue;
        dfs2(v, u);
        sum[u] += sum[v];
    }
    if(sum[u] > 0) dsu.join(s[u],s[pre]);
}

bool vis[SZ];
int leaf = 0;

void dfs3(int u, int pre)
{
    vis[u] = true;
    bool flag = false;
    for(int v : adj2[u])
    {
        if(v == pre) continue;
        flag = true;
        dfs3(v, u);
    }
    if(!flag) leaf++;
}

int main()
{
    init();
    cin >> n >> k;
    dsu.init(n);
    for(int i = 1; i < n; i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edges.pb({u,v});
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        vec[s[i]].pb(i);
    }
    dfs1(1, 0);
    for(int i = 1; i <= k; i++)
    {
        int root = vec[i][0];
        for(int j = 1; j < vec[i].size(); j++)
        {
            root = lca(root, vec[i][j]);
        }
        for(int j : vec[i])
        {
            sum[j]++;
        }
        sum[root] -= vec[i].size();
    }
    dfs2(1, 0);
    for(pii e : edges)
    {
        int u = dsu.get(e.fi), v = dsu.get(e.se);
        if(u == v) continue;
        adj2[u].pb(v);
        adj2[v].pb(u);
    }
    for(int i = 1; i <= k; i++)
    {
        if(adj2[i].size())
        {
            dfs3(i,0);
            break;
        }
    }
    if(leaf == 1) cout << 1;
    else cout << (leaf + 1) / 2;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:153:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for(int j = 1; j < vec[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 61496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -