제출 #604316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604316		talant117408	Mergers (JOI19_mergers)	C++17	0 / 100	160 ms	40348 KiB

mergers

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const int N = 5e5+7;
vector <int> graph[N], comps_graph[N];
int color[N], states[N], hanging, tmp_states[N], comp[N], num;
map <pii, bool> separators;

void dfs(int v, int p) {
    if (hanging == 0 && p) {
        separators[mp(min(v, p), max(v, p))] = 1;
    }
    tmp_states[color[v]]++;
    if (tmp_states[color[v]] == states[color[v]]) hanging--;
    if (tmp_states[color[v]] == 1) hanging++;
    for (auto to : graph[v]) {
        if (to == p) continue;
        dfs(to, v);
    }
    if (tmp_states[color[v]] == states[color[v]]) hanging++;
    if (tmp_states[color[v]] == 1) hanging--;
    tmp_states[color[v]]--;
}

void find_comps(int v, int p) {
    comp[v] = num;
    for (auto to : graph[v]) {
        if (to == p || separators[mp(min(v, to), max(v, to))]) continue;
        find_comps(to, v);
    }
}

void solve(int test) {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
        states[color[i]]++;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        if (!comp[i]) {
            num++;
            find_comps(i, i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto to : graph[i]) {
            if (comp[i] != comp[to]) {
                comps_graph[comp[i]].pb(comp[to]);
            }
        }
    }
    int ans = -1;
    for (int i = 1; i <= num; i++) {
        if (sz(comps_graph[i]) == 1 || sz(comps_graph[i]) == 0) ans++;
    }
    cout << ans << endl;
}  

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
    
    return 0;
}

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