제출 #1336633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336633		sh_qaxxorov_571	Mergers (JOI19_mergers)	C++20	컴파일 에러	0 ms	0 KiB

mergers

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 500005;
const int LOGN = 20;

vector<int> adj[MAXN], tree[MAXN];
vector<int> state_cities[MAXN];
int depth[MAXN], up[MAXN][LOGN];
int diff[MAXN], group[MAXN], deg[MAXN];
int n, k;

// LCA uchun tayyorgarlik
void dfs_lca(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p;
    for (int i = 1; i < LOGN; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u]) {
        if (v != p) dfs_lca(v, u, d + 1);
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) u = up[u][i];
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

// Qirralarni belgilash (Difference array on tree)
void dfs_diff(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs_diff(v, u);
            diff[u] += diff[v];
        }
    }
}

// Bir xil guruhga tegishli shaharlarni birlashtirish
void dfs_group(int u, int g) {
    if (diff[u] > 0) group[u] = g;
    else group[u] = u;
    
    int current_group = group[u];
    for (int v : adj[u]) {
        if (v != up[u][0]) {
            if (diff[v] > 0) dfs_group(v, current_group);
            else dfs_group(v, v);
        }
    }
}

// DSU orqali haqiqiy guruhlarni topish (Alternativ sodda usul)
int parent[MAXN];
int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        int s; cin >> s;
        state_cities[s].push_back(i);
    }

    dfs_lca(1, 1, 0);

    // Har bir shtat shaharlarini bog'lovchi yo'llarni belgilash
    for (int i = 1; i <= k; i++) {
        int lca = state_cities[i][0];
        for (int j = 1; j < state_cities[i].size(); j++) {
            lca = get_lca(lca, state_cities[i][j]);
        }
        diff[lca] -= (state_cities[i].size() - 1); // Bu qismda soddalashtirilgan diff logic
        for (int city : state_cities[i]) {
            diff[city]++;
            diff[lca]--;
        }
    }
    // Eslatma: Yuqoridagi diff logic i-shahar va uning shtatdagi LCA orasidagi 
    // barcha qirralarni belgilash uchun xizmat qiladi.

    dfs_diff(1, 1);

    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 2; i <= n; i++) {
        if (diff[i] > 0) {
            int u = find_set(i);
            int v = find_set(up[i][0]);
            if (u != v) parent[u] = v;
        }
    }

    // Yangi daraxt qurish
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            int root_u = find_set(u);
            int root_v = find

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:122:26: error: cannot resolve overloaded function 'find' based on conversion to type 'int'
  122 |             int root_v = find
      |                          ^~~~
mergers.cpp:122:30: error: expected '}' at end of input
  122 |             int root_v = find
      |                              ^
mergers.cpp:120:30: note: to match this '{'
  120 |         for (int v : adj[u]) {
      |                              ^
mergers.cpp:122:30: error: expected '}' at end of input
  122 |             int root_v = find
      |                              ^
mergers.cpp:119:34: note: to match this '{'
  119 |     for (int u = 1; u <= n; u++) {
      |                                  ^
mergers.cpp:122:30: error: expected '}' at end of input
  122 |             int root_v = find
      |                              ^
mergers.cpp:73:12: note: to match this '{'
   73 | int main() {
      |            ^