Submission #359118

#	Time	Username	Problem	Language	Result	Execution time	Memory
359118		erfanmir	Mergers (JOI19_mergers)	C++17	0 / 100	1 ms	620 KiB

mergers

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 2e3 + 10;
const int MAXLG = 11;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int n, k, par[MAXN][MAXLG], ans, head[MAXN], h[MAXN], col[MAXN], root, tmp;
bool mark[MAXN];
vector<int> adj[MAXN], vec[MAXN];
queue<int> q;

void dfs(int v){
    for(auto u : adj[v]){
        if(u == par[v][0]){
            continue;
        }
        h[u] = h[v] + 1;
        par[u][0] = v;
        dfs(u);
    }
}

int edq(int u, int val){
    for(int i = 0; i < MAXLG; i++){
        if(val & 1){
            u = par[u][i];
        }
        val /= 2;
    }
    return u;
}

int lca(int v, int u){
    if(h[v] > h[u]){
        swap(v, u);
    }
    u = edq(u, h[u] - h[v]);
    if(v == u){
        return v;
    }
    for(int i = MAXLG - 1; ~i; i--){
        if(par[u][i] == par[v][i]){
            continue;
        }
        v = par[v][i];
        u = par[u][i];
    }
    return par[v][0];
}

void cal(int v){
    if(h[v] < h[root]){
        return;
    }
    if(!mark[col[v]]){
        mark[col[v]] = true;
        tmp++;
        for(auto y : vec[col[v]]){
            q.push(y);
            root = lca(root, y);
        }
    }
    cal(par[head[v]][0]);
    head[v] = head[par[head[v]][0]];
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", col + i);
        vec[col[i]].push_back(i);
    }
    h[1] = 1;
    dfs(1);
    for(int j = 1; j < MAXLG; j++){
        for(int i = 1; i <= n; i++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
    ans = k;
    for(int i = 1; i <= k; i++){
        memset(mark, 0, sizeof mark);
        mark[i] = true;
        tmp = 1;
        for(int j = 1; j <= n; j++){
            head[j] = j;
        }
        int x = vec[i][0];
        for(int j = 1; j < (int)vec[i].size(); j++){
            x = lca(x, vec[i][j]);
        }
        root = x;
        for(int j = 0; j < (int)vec[i].size(); j++){
            q.push(vec[i][j]);
        }
        while(!q.empty()){
            cal(q.front());
            q.pop();
        }
        ans = min(ans, tmp - 1);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

mergers.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
mergers.cpp: In function 'int main()':
mergers.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%d", col + i);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30