제출 #248663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248663		fivefourthreeone	Mergers (JOI19_mergers)	C++17	0 / 100	101 ms	40816 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 cnt =0;
int sub[mxN];
vector<int> subans;
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]]];
    //cout<<u<<" "<<best[u]<<'\n';
    if(p==0&&u!=0) {
        sub[u] = cnt++;
        subans.senpai(0);
    }else if(p!=0) {
        sub[u] = sub[p];
    }
    for(int v: adj[u]) {
        if(v==p)continue;
        solve(v, u);
        if(flag[v]) {
            flag[u] = true;
        }
        best[u] = min(best[u], best[v]);
    }
    if(flag[u])return;
    if(depth[best[u]]==depth[u]&&u!=p) {
        subans[sub[u]]++;
        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);
    int left =0;
    int right = subans.size()-1;
    while(left<right) {
        if(subans[left]==0) {
            left++;
            continue;
        }
        if(subans[right]==0){
            right--;
            continue;
        }
        subans[left]--;
        subans[right]--;
        ans++;
    }
    ans+=subans[left];
    cout<<ans<<"\n";
    return 0;
}

컴파일 시 표준 에러 (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:113: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