제출 #1261472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261472		asdfghqwert	Mergers (JOI19_mergers)	C++20	0 / 100	130 ms	63052 KiB

mergers

#pragma GCC optimize("O3,Ofast,unroll-loops,fast-math")
//#pragma GCC optimize("O3,Ofast")
#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 5e5 + 100;
const int lg = 20;

int up[maxn][lg] , dep[maxn] , color[maxn];
vector<int> g[maxn];
vector<int> c[maxn];
vector<int> sholud_add[maxn];
void dfs(int u , int p){
    up[u][0] = p;
    for(int i = 1 ; i < lg ; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for(int &v : g[u]){
        if(v == p)continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
int lca(int u , int v){
    if(dep[u] < dep[v])swap(u , v);
    for(int i = lg - 1 ; i >= 0 ; i--){
        if(dep[u] - (1 << i) >= dep[v])
            u = up[u][i];
    }
    if(u == v)return u;
    for(int i = lg - 1 ; i >= 0 ; i--){
        if(up[u][i] != up[v][i]){
            v = up[v][i];
            u = up[u][i];
        }
    }
    return up[u][0];
}
int32_t main(){
    int n , k; cin >> n >> k;
    for(int i = 1 ; i < n ; i++){
        int u , v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> color[i];
        c[color[i]].push_back(i);
    }
    dfs(1 , 0);
    for(int i = 1 ; i <= k ; i++){
        if(c[i].empty())continue;
        int lc = c[i][0];
        for(int &p : c[i])lc = lca(lc , p);
        for(int &p : c[i])sholud_add[lc].push_back(p);
    }
    queue<int> prc;
    vector<bool> marked(n + 1);
    prc.push(1);
    marked[1] = 1;
    while(!prc.empty()){
        int u = prc.front();prc.pop();
        for(int v : sholud_add[u]){
            if(marked[v])continue;
            marked[v] = 1;
            prc.push(v);
        }
        u = up[u][0];
        while(marked[u] == 0 && u != 0){
            prc.push(u);
            marked[u] = 1;
            u = up[u][0];
        }
    }   
    int ans = 1;
    for(int i = 2 ; i <= n ; i++){
        if(marked[up[i][0]] && !marked[i])ans++;
    }
    cout << (ans) / 2;
}

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