Submission #248662

#	Time	Username	Problem	Language	Result	Execution time	Memory
248662		fivefourthreeone	Mergers (JOI19_mergers)	C++17	0 / 100	128 ms	39920 KiB

mergers

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
vector<int> adj[mxN];
int n, k;
vector<int> state[mxN];
int high[mxN];
int depth[mxN];
int val[mxN];
int par[mxN][21];
bool flag[mxN];
int best[mxN];
int ans = 0;
int walk(int a, int b) {
    uwu(lg, 21, 0) {
        if(b&(1<<lg)) {
            a = par[a][lg];
        }
    }
    return a;
}
int lca(int a, int b) {
    if(depth[a]<depth[b]) {
        walk(b, depth[b]-depth[a]);
    }else if(depth[a]>depth[b]) {
        walk(a, depth[a]-depth[b]);
    }
    if(a==b)return a;
    uwu(lg, 21, 0) {
        if(par[a][lg]!=par[b][lg]) {
            a = par[a][lg];
            b = par[b][lg];
        }
    }
    return par[a][0];
}
void dfs(int u, int p) {
    par[u][0] = p;
    for(int v: adj[u]) {
        if(v==p)continue;
        depth[v] =depth[u]+1;
        dfs(v, u);
    }
}
void solve(int u, int p) {
    best[u] = depth[high[val[u]]];
    for(int v: adj[u]) {
        if(v==p)continue;
        solve(v, u);
        if(flag[v]) {
            flag[u] = true;
            return;
        }
        best[u] = min(best[u], best[v]);
    }
    //cout<<u<<" "<<best[u]<<"\n";
    if(depth[best[u]]==depth[u]&&u!=p) {
        ans++;
        flag[u] = true;
    }
}
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    int a, b;
    owo(i, 0, n-1) {
        cin>>a>>b;
        a--; b--;
        adj[a].senpai(b);
        adj[b].senpai(a);
    }
    owo(i, 0, n) {
        cin>>a;
        a--;
        val[i] = a;
        state[a].senpai(i);
    }
    dfs(0, 0);
    owo(lg, 1, 21){
        owo(i, 0, n) {
            par[i][lg] = par[par[i][lg-1]][lg-1];
        }
    }
    owo(i, 0, k) {
        int comlca = state[i][0];
        owo(j, 1, state[i].size()) {
            comlca = lca(comlca, state[i][j]);
        }
        high[i] = comlca;
        //cout<<i<<" "<<high[i]<<"\n";
    }
    solve(0, 0);
    cout<<((ans+1)/2)<<"\n";
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:2:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a); i<(b); ++i)
                                     ^
mergers.cpp:104:9: note: in expansion of macro 'owo'
         owo(j, 1, state[i].size()) {
         ^~~

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